描述

给定一个整数数列和一些查询，每个查询要求找出数列中某个区间内的最大元素。 例如，对于数列9，8，55，-5，10。区间[3，4]的最大元素是10，区间[0，3]的最大元素是55。

输入输出格式

输入

第一行：一个正整数n，代表数列的项数

第二行：用空格隔开的n个整数，代表数列的每一项

第三行：一个整数m，代表需要查询的区间的数目

第四行到第m+3行：每一行有两个空格隔开的非负整数a和b，代表区间范围，a ≤ b。

输出

m行，每一行代表对应区间的最大值。

样例

5
9 8 55 -5 10
3
3 4
0 3
1 1

10
55
8