#include <bits/stdc++.h>
using namespace std;
struct dsu{
vector<int>root;
vector<int>siz;
vector<int>val;
vector<int>l;
vector<int>r;
dsu(int n){
root=vector<int>(n);
siz=vector<int>(n,1);
val=vector<int>(n);
l=vector<int>(n);
r=vector<int>(n);
iota(root.begin(),root.end(),0);
iota(l.begin(),l.end(),0);
iota(r.begin(),r.end(),0);
}
int findRoot(int x){
if(x==root[x])
return x;
return root[x]=findRoot(root[x]);
}
bool unite(int x, int y){
x=findRoot(x);
y=findRoot(y);
if(x==y){
return 0;
}
if(siz[x]<siz[y]){
swap(x,y);
}
siz[x]+=siz[y];
root[y]=x;
val[x]=max(val[x],val[y])+1;
l[x]=min(l[x],l[y]);
r[x]=max(r[x],r[y]);
return 1;
}
};
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,q;
cin >> n >> q;
int arr[n];
for(int &i : arr){
cin >> i;
}
while(q--){
int l,r;
cin >> l >> r;
l--;r--;
vector<int>ls(r-l+1);
dsu ds(r-l+1);
priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>>pq;
for(int i = l;i<=r;i++){
ls[i-l]=arr[i];
ds.val[i-l]=arr[i];
pq.push({arr[i],i-l});
}
while(!pq.empty()){
array<int,2>a = pq.top();
pq.pop();
a[1]=ds.findRoot(a[1]);
if(a[0]!=ds.val[a[1]]){
///this one was already merged. continue
continue;
}
int lef = (ds.l[a[1]]!=0) ? ds.findRoot(ds.l[a[1]]-1) : -1;
int rig = (ds.r[a[1]]!=(r-l)) ? ds.findRoot(ds.r[a[1]]+1) : -1;
lef=(lef!=-1) ? ds.findRoot(lef) : -1;
rig=(rig!=-1) ? ds.findRoot(rig) : -1;
int lefval = (lef!=-1) ? ds.val[lef] : 1e9;
int rigval = (rig!=-1) ? ds.val[rig] : 1e9;
if(lefval<=a[0]){
///merge with this
ds.unite(lef,a[1]);
pq.push({ds.val[ds.findRoot(a[1])],a[1]});
}
else if(rigval<=a[0]){
///merge with this
ds.unite(rig,a[1]);
pq.push({ds.val[ds.findRoot(a[1])],a[1]});
}
else{
///decide later
}
}
assert(ds.siz[ds.findRoot(0)]==(r-l+1));
cout << ds.val[ds.findRoot(0)] << "\n";
}
return 0;
}
