该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有$n$个产品按一定的顺序排列在展示架上，从前往后第$i$个位置的产品是编号为$t_i$的产品。

请处理 $m$个查询，每个查询如下：

给定两个整数$x_i$ 和$y_i$。在编号为 $x_i$ 的产品和编号为$y_i$的产品中，输出排在更前面的那个产品的编号。

输入格式

第一行，一个正整数$n$，表示产品的数量。
第二行，$n$个用空格隔开的正整数，表示产品的编号。
第三行，一个正整数$m$，表示询问的次数。
接下来$m$行，每行两个数，分别表示当次查询的$x_i$和$y_i$。

输出格式

输出$m$行。第$i$行表示第$i$次查询的答案。

样例

输入样例1

3
2 1 3
3
2 3
1 2
1 3

输出样例1

2
2
1

输入样例2

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

输出样例2

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

数据范围

对于$50\%$的数据，$1\le t_i\le n,m\le 1000$，$1\le x_i < y_i \le n$

对于$100\%$的数据，$1\le t_i\le n,m\le 10^6$，$1\le x_i < y_i \le n$，对于任意的$i\ne j$，有$t_i \ne t_j$

样例解释 1

在第一个查询中，编号为 2 的产品在最前面，编号为 3 的产品在第三位，因此编号为 2 的产品站得更靠前。

在第二个查询中，编号为 1 的产品站在第二位，编号为 2 的产品站在最前面，因此编号为 2 的产品站得更靠前。

在第三个查询中，编号为 1 的产品站在第二位，编号为 3 的产品站在第三位，因此编号为 1 的产品站得更靠前。

样例解释 2

对于给出的查询，通过比较两个产品在展示架上的位置即可得到答案。排在更前面的产品编号将被输出。