说明

给$n$个数，下标从$0$到$n-1$，有$q$个询问，每个询问给$l$和$r$，输出下标从$l$到$r$的数的最大值

$n=1000000,q=10000,0 \le l \le r \lt n$

已知在题目时限范围内判题机的运算次数约为$1e8$

如果你每次都直接暴力计算$l$到$r$的最大值，那每次最多可能比较$n$次

那么整个问题的最多比较次数约为$qn=1e10$，是会超时的

事实上，针对此问题，有专门的基于倍增和动态规划的ST算法，它能在约为$nlog_{2}n + q \approx 2e7$的运算级别解决此问题

或者利用线段树，也能在约为$4n + qlog_{2}n \approx 4e6$的运算级别解决此问题

如果你之前已经学过这两个算法，那么现在你可以开始你的表演了

如果没有的话，那么在这里，我教给你另一种算法——分块：

将$n$个数分成$x$个块，每块包含$m=\frac {n}{x}$个数，第$0$块下标从$0$到$m-1$，第$1$块下标从$m$到$2m-1$，···，第$x-1$块下标从$(x-1)m$到$n-1$

提前算出每个块中数的最大值

对于每次询问，我们可以求出$l$和$r$所在的块，$l$在第$\frac {l}{m}$块，$r$在第$\frac {r}{m}$块

如果$l$和$r$在同一个块：直接暴力计算$l$到$r$的最大值，由于一个块大小为$\frac {n}{x}$，所以最多比较$\frac {n}{x}$次

如果$l$和$r$在不同块：

①暴力计算$l$到其块尾的最大值，最多比较$\frac {n}{x}$次

②计算$l$所在块到$r$所在块之间的数的最大值，由于已经预先处理了每个块中数的最大值，所以这一段可以一块一块地比较，最多有$x$个块，需要比较$x$次

③暴力计算$r$所在块首到r的最大值，最多比较$\frac {n}{x}$次

①②③之和为$\frac {2n}{x}+x$

所以对于每次询问，我们的比较次数为$\frac {n}{x}$或$\frac {2n}{x}+x$，当$x$取$\sqrt{n}$时，两者均为$\sqrt{n}$级别，达到一个平衡点

所以整个问题的最多比较次数约为$q\sqrt{n} = 1e7$，在时限范围内

输入格式

第一行为$n$，第二行有$n$个小于$1000000$的正整数，第三行为$q$，接下来有$q$行，每行一个$l$和$r$

输出格式

输出$q$行，每行一个数代表询问的答案

样例

5
3 6 1 8 9
5
0 4
0 3
2 2
2 3
3 4

9
8
1
8
9

提示

样例只是为了帮助你理解问题，实际数据中$n$一定为$1000000$，$q$一定为$10000$