303 - RMQ问题

通过次数

26

提交次数

72

时间限制 : 3 秒
内存限制 : 256 MB

RMQ问题:Range Minimum/Maximum Query

输入一串数字,给你M个询问,每次询问就给你两个数字L,R,要求你说出L到R这段区间内的最大数。

输入

第一行两个整数N,M表示数字的个数和要询问的次数;

接下来一行为N个数;

接下来M行,每行都有两个整数X,Y。

输出

输出共M行,每行输出一个数。

样例

输入

10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8

输出

5
8

提示

【数据规模】

对于全部数据,1<=N<10^5,1<=M<=10^6,1<=X<=Y<=N

数字不超过 C/C++int 范围。