腹ペコのムト

시간 제한1.5초메모리 제한512 MB

요약

각 재료를 한 번 진화시킨 결과가 주어질 때, f(x) = f^c(x)를 만족하는 시작 재료 x의 개수를 각 질의 c마다 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 수학, 정수론
정답자: 아직 제출이 없습니다

문제

무토는 재료를 모아서 음식을 만들어 먹곤 합니다. 오늘도 어김없이 배가 매우 고팠던 무토. 마침, $1$ 번부터 $n$ 번까지 번호가 매겨진 서로 다른 $n$ 개의 포켓몬 재료가 무토의 눈에 보였습니다. 이 재료들은 $1$ 번 진화시키면 다른 포켓몬 재료로 변합니다. 요리를 만들다가 심심해진 무토는 여러분들에게 다음 질문을 $Q$ 번 하였습니다.

삐돌이와 삐미가 $x$ 번 재료를 가지고 게임을 시작해. 삐돌이는 $x$ 번 재료를 $1$ 번 진화시키고, 삐미는 $x$ 번 재료를 $c$ 번 진화시킬 거야. 삐돌이의 결과와 삐미의 결과가 같게 하는 $x$ 의 개수는 몇 개인지 알고 싶어.

$Q$ 개의 질문을 해결해 주세요.

입력

첫 번째 줄에 포켓몬 재료의 수 $n$ 이 주어집니다.

두 번째 줄에 $n$ 개의 정보가 공백으로 구분되어 주어집니다. 이때, $i$ 번째 수는 $i$ 번 재료가 $1$ 번 진화하면 $x\_{i}$ ( $1 ≤ x\_{i} ≤ n$ )번 재료가 됨을 의미합니다. 단, 재료의 진화 전과 후는 같을 수 있습니다.

그다음 줄에 질문의 개수 $Q$ 가 주어집니다.

그다음 줄부터 $Q$ 개의 줄에 걸쳐 쿼리에 대한 정보 $q$ 가 주어집니다. 이는 무토의 질문에서 $c$ 가 $q$ 임을 의미합니다.

출력

무토의 질문에 대한 정답을 $Q$ 개의 줄에 출력해 주세요.

제한

$1 ≤ n ≤ 500\\,000$
$1 ≤ Q ≤ 500\\,000$
$1 ≤ q ≤ 2\\,000\\,000$

예제2

예제 1
입력
```
3
1 3 2
2
1
2
```
예상 출력
```
3
1
```
예제 2
입력
```
2
1 2
2
3
4
```
예상 출력
```
2
2
```