题目背景

话说 loidc 现在正在家闲的无聊，这天 loidc 正在观看比赛，他突然很有兴趣想了解一段时间内中国队获得金牌的情况。

题目描述

还有一点，loidc 有特殊能力，可以预知未来，他可以准确的猜到中国队在某一个单位时间内获得的金牌数。但是，还有但是！由于工作量太大，再加上猜金牌要费很多的体力，所以他无法准确的计算出一段时间内获得的金牌数最大的单位时间是哪个，就因为这样 loidc 很郁闷。他思索来思索去就想到了你，因为他知道你是个 OIer，所以他对你呵呵一笑就把问题交给你了，loidc 希望你能在 1 s 内得出答案。

输入格式

第一行一个 $n$，表示有 $n$ 个时间段。

接下来一行有 $n$ 个数 $a_i$，$a_i$ 表示 loidc 猜到的中国队在第 $i$ 个时间段内获得的金牌数。

然后，第三行有一个数 $m$，表示 loidc 有个问题。

接下来有 $m$ 行，每行有 $2$ 个数分别为 $x_i$，$y_i$，表示要询问在时间段 $[x_i,y_i]$ 内中国队获得金牌数最大的是哪个单位时间。

loidc 有一个习惯，他问问题是有先后的，也就是说后一个问题总是在前一个问题之后提出的。

注意对于第 $i$ 个提问和第 $i+1$ 个提问严格的有 $x_i \le x_{i+1}$、$y_i \le y_{i+1}$。

输出格式

一共 $m$ 行，每行一个 $k_i$，表示第 $i$ 个询问的答案。

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

1
2
3
4
5

提示

$30\%$：$n \le 1000$，$m \le 1000$。

$100\%$：$n \le {10}^5$，$m \le {10}^5$。

其他有关输入输出均小于 maxlongint。

数据保证 $a_i$ 没有相同的。