Description

给定 $n$ 个数和 $m$ 组询问，每次求给定区间中的最大值。

Input Format

第一行，数字 $n$，表示共有 $n$ 个数字，接下来的 $n$ 行每行一个整数 $a_i$。

接下来一行一个整数 $m$，表示有 $m$ 组询问；

接下来若干行，每行两个正整数 $l_i$ 和 $r_i$ 表示查询区间 $[l, r]$ 的最大值。

Output Format

$m$ 行，分别为要求查询的各区间的最大值。

Sample

样例输入

6
8
2
0
6
7
4
3
1 3
3 6
2 4

样例输出

8
7
6

Hint

$1 \leq n \leq 10 ^ 5$，$-10 ^ 6 \leq a_i \leq 10 ^ 6$，$1 \leq m \leq 10 ^ 5$。