问题 3736 --极值问题

3736: 极值问题

时间限制: 1 Sec  内存限制: 256 MB
提交: 88  解决: 21
[提交][状态][讨论版][命题人:]

题目描述

给出n个整数，接下来有q次询问，每次询问会给出两个正整数i,j，（1<=i<=n,1<=i+2^j-1<=n)，令k=2^j,则对于每次询问，给出以从第i个数开始的k个整数中的最大值。


输入

第一行：输入两个个整数n，q(1<=n,q<=10^6)
第二行：输入n个整数ai,(-10^9<=ai<=10^9)
接下来q行，每行输入两个整数qi,qj.(1<=qi<=n,1<=qi+2^qj-1<=n)。

输出

一共q行，每行一个整数，对应每次查询的结果。

样例输入

5 1
1 2 3 4 5
1 2

样例输出

4

提示


1<=n,q<=10^6



-10^9<=ai<=10^9

来源

区间dp 

[提交][状态]