题目描述

小林很喜欢户外徒步，这天他来到一条乡间公路，这条公路的一边整整齐齐的种着一排树。

他从路口出发，沿着公路边走边数树的数量，总共有$\red n$棵树，每棵树的高度又不同。

假如每棵树的高度已知，现在给这$\red n$棵树编号，路口处的树为第$\red 1$棵，接着为第$\red 2$棵，以此递增，一直到尽头的第$\red n$棵树。

若给定$\red m$组区间，每组区间有两个整数$\red l$和$\red r$，那么在第$\red l$棵树和第$\red r$棵树之间，哪棵树最高，输出树的高度。

输入格式

第一行，一个整数$\red n$，即有$\red n$个数；

第二行，$\red n$个整数，数与数之间用空格隔开；

第三行，一个整数m，即有$\red m$组区间；

接下来的$\red m$行，每行有两个整数$\red l$和$\red r$，表示一个区间，$\red l$与$\red r$用空格隔开。

输出格式

有$\red m$行输出，每行有一个数，即对应区间的最大值。

样例

输入样例

8
1 6 3 5 12 7 29 9
4
1 3
4 5
3 8
2 7

输出样例

6
12
29
29

提示

所有数据满足： $\red{1 \le n \le 1000，1 \le m \le n，1 \le l，r \le n}$。