题目描述

给定一个长度为 N（1 ≤ N ≤ 1000）的整数数组，数组元素由输入给定。现需进行 Q 次（1 ≤ Q ≤ 1000）区间最大值查询，每次查询要求计算数组的某段连续区间 [L, R] 内所有元素的最大值。请输出每次查询的结果。

输入格式

输入共分为三部分：

1. ​​第一行​​：一个整数 N，表示数组的长度。
2. ​​第二行​​：包含 N 个整数，用空格分隔，表示数组的初始元素值（每个元素为整数，范围在 [-1e9, 1e9] 内）。
3. ​​第三行​​：一个整数 Q，表示查询次数。
4. ​​接下来 Q 行​​：每行包含两个整数 L 和 R（1 ≤ L ≤ R ≤ N），表示查询的区间范围。

​​注意​​：

• 数组下标从 1 开始（即区间 [1, N]）。

输出格式

输出共 Q 行，每行一个整数，表示对应查询区间的最大值。

样例

输入样例

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

5
4
5

样例解释

1. 初始数组为 [3, 1, 4, 2, 5]。
2. 第一次查询区间 [1, 5] 的最大值为 max(3,1,4,2,5) = 5。
3. 第二次查询区间 [2, 3] 的最大值为 max(1,4) = 4。
4. 第三次查询区间 [4, 5] 的最大值为 max(2,5) = 5。

数据范围

• N 和 Q 的最大值均为 1000。
• 数组元素的取值范围为 [-1e9, 1e9]。
• 输入保证所有查询区间合法（1 ≤ L ≤ R ≤ N）。