时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Bob 有 n 个数，他想知道任意一个区间内的最大值是多少。
输入描述:
第一行一个整数 n，表示数的个数，其中 n<=10^6；
第二行为 n 个整数。
第三行一个整数 q，表示询问的次数，其中 q<=10^6；
接下来 q 行，每行有一对 L,R，即询问区间 [L,R] 的最大值。
输出描述:
q 行，每一次询问的结果。
示例1
输入
复制
5
10 4 6 2 9
3
1 3
2 4
3 5
备注:
注意此题输入量极大，需要使用输入优化。