一番战斗之后，程序猿被计算鸡们赶走了。随着垫子计算鸡一声令下：“追！”，于是计算鸡村全村上下开始乘胜追击。计算鸡们希望在新的一年到来之际给程序猿以重创，出掉这一年的恶气。

可是程序猿一追就走，一走就跑，一跑就无影无踪。计算鸡们开始跋山涉水寻找程序猿的踪迹。快乐游戏鸡跟随大部队走着走着，突然说道：“我好像打过类似的游戏”。

快乐游戏鸡玩过的游戏是这样的：给定一棵 $n$ 个结点的树，其中 $1$ 号结点是根。每次玩家可以在树上行走，走过一条边需要 $1$ 秒的时间，但只能往当前所在的点的某个儿子走，不能往父亲走。每次游戏需要从 $s$ 号结点走到 $t$ 号结点去。

玩家有一个总死亡次数，初始为 $0$。每个结点上有一个程序猿和一个参数 $w_i$，如果走到结点 $i$ 的时候，当前总的死亡次数小于 $w_i$，那么玩家就会立刻死亡并回到起点 $s$，且该死亡过程不需要时间；如果总死亡次数大于等于 $w_i$，那么玩家就能熟练地对付程序猿从而安然无恙。注意每次游戏时不需要考虑 $s$ 和 $t$ 上的程序猿。

该游戏会进行若干轮，每轮会清空总死亡次数并给出一组新的 $s, t$。现在请你对于每一轮游戏输出走到 $t$ 所需要的最短时间（单位为秒）。

保证每个询问的 $s$ 可以到达 $t$。

输入格式

第一行一个正整数 $n$，表示树的结点数。

第二行 $n$ 个正整数，其中第 $i$ 个表示 $w_i$。

第三行 $n-1$ 个整数，第 $i$ 个表示 $i+1$ 号点的父亲结点 $f_i$，保证 $f_i < i$ 。

第四行一个正整数 $q$ 表示游戏轮数。

接下来 $q$ 行，每行两个整数 $s,t$，表示一轮游戏。

输出格式

输出 $q$ 行，每行一个整数表示每轮游戏的答案。

5
1 1 2 4 4
1 1 2 4
1
1 5

9

由于题面提到每次询问 $s,t$ 的时候不考虑 $s$ 和 $t$ 上的程序猿，所以首先我们无视点 $1$ 和点 $5$ 的程序猿。

一种可能的方案：

1. 死亡次数为 $0$ 时，从点 $1$ 走到点 $2$ 碰到程序猿，死亡，回到点 $1$，耗时 $1$ 秒；
2. 死亡次数为 $1$ 时，从点 $1$ 走到点 $3$ 碰到程序猿，死亡，回到点 $1$，耗时 $1$ 秒；
3. 死亡次数为 $2$ 时，从点 $1$ 走到点 $4$ 碰到程序猿，死亡，回到点 $1$，耗时 $2$ 秒；
4. 死亡次数为 $3$ 时，从点 $1$ 走到点 $4$ 碰到程序猿，死亡，回到点 $1$，耗时 $2$ 秒；
5. 死亡次数为 $4$ 时，从点 $1$ 走到点 $5$，耗时 $3$ 秒。

总耗时 $9$ 秒。

8
10 4 2 3 1 6 2 7
1 2 3 4 1 6 7
5
1 5
1 8
2 4
2 5
3 3

8
9
4
7
0

样例三

见样例数据下载。该样例满足子任务 $2$ 条件。

样例四

见样例数据下载。该样例满足子任务 $4$ 条件。

限制与约定

由于一些原因，本题使用捆绑测试。每个子任务有若干个测试点，分为 5 个子任务，你只有通过一个子任务的所有测试点才能得到这个子任务的分数。

对于所有数据，保证 $1 \leq n,q \leq 3 \times 10^5$ 且 $1 \leq w_i \leq 10^9$ 且 $f_i < i$ 且 $1 \leq s,t \leq n$。

时间限制：$2\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载