33523번 - 체리 컴퍼니

문제

체리 컴퍼니는 국내 유일무이 체리 전문 디저트 회사이다. 회사의 직원은 총 $N$명이며, 각 직원은 1ドル$부터 $N$번까지의 고유한 사원 번호를 가진다. 1ドル$번 직원은 회사의 사장이며 직속상관이 없다. 1ドル$번 직원을 제외한 나머지 직원은 한 명의 직속상관을 가지며, $i$번 직원의 직속상관의 사원 번호 $P_i$는 $i$보다 작다.

체리 컴퍼니는 새로운 디저트 출시를 위해 $Q$일 동안 매일 회의가 열린다. 각 날마다 회의는 아래 과정을 거쳐 소집된다.

• 체리 컴퍼니는 탄력 근무제를 시행하고 있어 $i$번째 날에는 사원 번호가 $L_i$ 이상 $R_i$ 이하인 직원만 출근한다.
• 출근한 직원 중 자신의 직속상관이 출근한 직원은 직속상관과 같은 회의에 참석한다.
• 출근한 직원 중 자신의 직속상관이 출근하지 않은 직원은 새로운 회의를 소집한다.
• 출근하지 않은 직원은 해당 날짜에 열리는 회의에 영향을 주지 않는다.

$\left(N, L_i, R_i\right)=\left(5, 2, 4\right)$일 때 회의가 열린 모습

위 그림은 체리 컴퍼니의 조직도에 출근한 직원들과 소집된 회의를 나타낸 예시이다.

주어진 조건에서 $i$번째 날에 소집되는 회의의 개수를 출력하시오.

입력

첫 번째 줄에 직원의 수를 나타내는 정수 $N$이 주어진다. $(2 \leq N \leq 300,000円)$

두 번째 줄에 $i(2 \leq i \leq N)$번 직원의 직속상관의 사원 번호를 나타내는 $N - 1$개의 정수 $P_2, \cdots, P_N$이 공백으로 구분되어 주어진다. $(1 \leq P_i < i)$

세 번째 줄에 회의가 열리는 날의 수를 나타내는 정수 $Q$가 주어진다. $(1 \leq Q \leq 300,000円)$

다음 $Q$개의 줄에 걸쳐, $i$번째 줄에 $i$번째 날에 출근하는 직원의 사원 번호 범위를 나타내는 두 정수 $L_i$과 $R_i$이 공백으로 구분되어 주어진다. $(1 \leq L_i \leq R_i \leq N)$

출력

$Q$개의 줄에 걸쳐 $i$번째 날에 소집되는 회의의 개수를 한 줄에 하나씩 출력한다.

제한

힌트