beecrowd | 3029

# Function Composition

By Microsoft Serbia

Timelimit: 1

We are definitely not going to bother you with another generic story when Alice finds about an array or
when Alice and Bob play some stupid game. This time you’ll get a simple, plain text.

First, let us define several things. We define function F on the array A such that F(i, 1) = A[i] and
F (i, m) = A[F (i, m − 1)] for m > 1. In other words, value F (i, m) represents composition A[...A[i]]
applied m times.

You are given an array of length N with non-negative integers. You are expected to give an answer on Q queries. Each query consists of two numbers – m and y. For each query determine how many x exist such that F(x, m) = y.

## Input

The first line contains one integer N (1 ≤ N ≤ 2 · 105 ) – the size of the array A. The next line contains N non-negative integers – the array A itself (1 ≤ AiN ). The next line contains one integer Q (1 ≤ Q ≤ 105 ) – the number of queries. Each of the next Q lines contain two integers m and y (1 ≤ m ≤ 1018 , 1 ≤ yN ).

## Output

Output exactly Q lines with a single integer in each that represent the solution. Output the solutions in the order the queries were asked in.

 Input Sample Output Sample 10 2 3 1 5 6 4 2 10 7 7 5 10 1 5 7 10 6 1 1 10 8 3 0 1 1 0