序列区间最大值
题目描述
给定一个序列a[n],并且进行m次询问,每次询问输入两个整数l,r,表示询问a[n]的子区间[l,r]中最大的数
子区间的含义:序列a[n]的子区间[l,r]表示一个所有的 a[i]_(l<=i<=r)组成的集合
注意:序列a[n]的序号从1开始,编号到n
输入
第一行,两个整数n,m
第二行,n个整数,表示给定的序列
第3到m+2行,每行两个整数,表示l和r
输出
输出共m行,每行一个整数,对于每个询问依次输出对应区间的最大值
输入样例
5 3
2 4 3 1 5
1 2
2 4
1 5
输出样例
4
4
5
数据范围和限制
对于30分的数据,有n<=4000,m<=5000
对于60分的数据,有n<=4000,m<=500000
对于100分的数据,有n<=200000,m<=500000，1≤l≤r≤n，0≤a[i]≤10^9
时间限制1s,空间限制512M
