[R1D]传送 - 代码源竞赛平台

时空限制

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$ 秒后你的位置。

输出格式

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

样例

样例输入 #1

5
2 3 5 4 1
2
1 3
4 10086

样例输出 #1

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$
4~5		$\leq 2\times 10^5$	$\leq 10$
6~10		$\leq 10^9$	$\leq 2\times 10^5$