题目描述

给定一个n个点以结点1为根的树，有q次询问，每次询问给出两个点u,v，求LCA(u, v)。

LCA(u, v)表示u, v的最近公共祖先。

输入描述

第一行一个整数n表示结点个数。(1 \le n \le 2 \times 10^5)

第二行n - 1个整数，表示2 \sim n结点的父亲。

第三行一个整数q，表示询问次数。(1 \le q \le 2\times 10^5)

接下来q行，每行两个整数u, v。(1 \le u, v \le n)

输出描述

对于每次询问，一行一个整数表示结果。

输入样例1

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

输出样例1

1
2
1