题目背景

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

题目描述

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

输入格式：

第一行一个n表示有n个时间段。
接下来一行有n个数ai，ai表示loidc猜到的中国队在第i个时间段内获得的金牌数。
然后，第三行有一个数m，表示loidc有个问题。
接下来有m行，每行有2个数分别为xi yi，表示要询问在时间段[xi,yi]内中国队获得金牌数最大的是哪个单位时间。
loidc有一个习惯，他问问题是有先后的，也就是说后一个问题总是在前一个问题之后提出的。
注意对于第i个提问和第i+1个提问严格的有xi<=xi+1，yi<=yi+1。

输出格式：

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

输入样例#1：

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

输出样例#1：

1
2
3
4
5

数据范围：

30%： n<=1000 m<=1000
100%： n<=100000 m<=100000
其他有关输入输出均小于maxlongint。
数据保证ai没有相同的。