//线段树,维护区间内所有元素的最大值
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 100005;
int n,m;
int a[N];
struct Node
{
int l,r;
int maxnum;
}tr[4*N];
void pushup(int u)
{
tr[u].maxnum=max(tr[u<<1].maxnum,tr[u<<1|1].maxnum);
}
void build(int u,int l,int r)
{
if(l==r)//build的递归终止条件:build到了最下层
tr[u]={l,r,a[r]};//l和r也要初始化,勿忘!
else
{
tr[u]={l,r};//l和r仍然要初始化,勿忘!
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
//下层处理完更新这个结点,勿忘!
pushup(u);
}
}
int query(int u,int l,int r)//强调:这里指的是查询u结点中与[l,r]交集部分的最大值
{
if(tr[u].l>=l&&tr[u].r<=r)//完全包含,则结束
return tr[u].maxnum;
int mid=tr[u].l+tr[u].r>>1;
int maxnum=1-pow(2,32);//-0x3f3f3f3f在这题的2^32-1要求中还不够大,故这样写了
if(l<=mid)//左边区间还有元素没查到
maxnum=max(maxnum,query(u<<1,l,r));
if(r>mid)//右边区间还有元素没查到
maxnum=max(maxnum,query(u<<1|1,l,r));
return maxnum;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,1,n);
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",query(1,x,y));
}
return 0;
}