32785번 - 腹ペコのムト

무토는 재료를 모아서 음식을 만들어 먹곤 합니다. 오늘도 어김없이 배가 매우 고팠던 무토. 마침, $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$