D. [R1D]传送

Type: Default

1000ms

512MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

给定 $n$ 个格子和一个长度为 $n$ 的正整数数组 $A_1,A_2,...,A_n$ ，当你位于格子 $i$ 时，下一秒你会被传送到格子 $A_i$ 。

有 $q$ 个询问，第 $i$ 个询问需要求如果初始位于格子 $s_i$ ， $c_i$ 秒后你的位置。

第一行包含一个正整数 $n$ ，表示格子的数量。

第二行包含 $n$ 个正整数，分别表示位于每个格子时下一秒的传送位置。

第三行包含一个正整数 $q$ ，表示询问的数量。

接下来 $q$ 行，每行包含两个正整数 $s_i$ 和 $c_i$ ，表示询问如果初始位于格子 $s_i$ ， $c_i$ 秒后你的位置。

对于每个询问，在单独的一行中输出一个整数，表示答案。

5
4

对于 $100\%$ 的数据， $1\leq n,q\leq 2\times 10^5$ ， $1\leq A_i,s_i\leq n$ ， $1\leq c_i\leq 10^9$ 。

测试点编号	$n$	$c_i$	$q$
1~2	$\leq 2000$	$\leq 20000$	$\leq 2\times 10^5$
3	$\leq 2\times 10^5$	$\leq 20$	$\leq 2\times 10^5$
4~5		$\leq 2\times 10^5$	$\leq 10$
6~10		$\leq 10^9$	$\leq 2\times 10^5$