题目描述

有 $N$ 个人排成一队。从前数第 $i$ 个人的编号为 $P_i$。 处理 $Q$ 个询问。第 $i$ 个询问如下： 给定整数 $A_i$ 和 $B_i$。在编号为 $A_i$ 的人和编号为 $B_i$ 的人中，输出站在更前面的人的编号。

输入格式

输入按以下形式给出： $N$ $P_1$ $\ldots$ $P_N$ $Q$ $A_1$ $B_1$ $\vdots$ $A_Q$ $B_Q$

输出格式

输出 $Q$ 行。第 $i$ 行应包含第 $i$ 个询问的答案。

样例

3
2 1 3
3
2 3
1 2
1 3

2
2
1

7
3 7 2 1 6 5 4
13
2 3
1 2
1 3
3 6
3 7
2 4
3 7
1 3
4 7
1 6
2 4
1 3
1 3

3
2
3
3
3
2
3
3
7
1
2
3
3

2
1 2
1
1 2

1

数据范围

• 所有输入均为整数。
• $1 \leq N \leq 100$
• $1 \leq P_i \leq N$，且 $P_i$ 两两不同（形成 $1$ 到 $N$ 的排列）。
• $1 \leq Q \leq 100$
• $1 \leq A_i < B_i \leq N$