#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)
int n,q;
int arr[300023];
int lg[300023];
int table[300023][19];
pair<int,int>sor[300023];
int ans[300023];
vector<int>v[1000023];
int iki[1000023];
int query(int l,int r){
if(l>r)return 0;
int s=lg[r-l+1];
int a=table[l][s];
int b=table[r+1-(1<<s)][s];
if(arr[b]>=arr[a])return b;
return a;
}
pair<vector<pair<int,int>>,vector<pair<int,int>>> dfs(int left,int right){
int mx=arr[query(left,right)];
int p=right+1;
vector<vector<pair<int,int>>>pre,su;
vector<int>ps;
while(p>left){
int p2=query(left,p-1);
if(arr[p2]!=mx){
auto res=dfs(left,p-1);
pre.pb(res.fr);
su.pb(res.sc);
break;
}
if(p2!=p-1){
auto res=dfs(p2+1,p-1);
pre.pb(res.fr);
su.pb(res.sc);
}
p=p2;
ps.pb(p);
pre.pb({{p,p}});
su.pb({{p,p}});
}
reverse(ps.begin(),ps.end());
reverse(pre.begin(),pre.end());
reverse(su.begin(),su.end());
vector<pair<int,int>>pref,suf;
for(int i=0;i<pre.size();i++){
int mx2=arr[query(pre[i][0].fr,pre[i].back().sc)];
if(mx2==mx){
pref.pb(pre[i][0]);
continue;
}
int kalan=0,las;
for(int j=0;j<pre[i].size();j++){
if(kalan==0){
las=pre[i][j].fr;
kalan=iki[mx-mx2];
}
kalan--;
if(kalan==0||j+1==pre[i].size()){
pref.pb({las,pre[i][j].sc});
continue;
}
}
}
for(int i=su.size()-1;i>=0;i--){
int mx2=arr[query(su[i][0].fr,su[i].back().sc)];
if(mx2==mx){
suf.pb(su[i][0]);
continue;
}
int kalan=0,las;
for(int j=su[i].size()-1;j>=0;j--){
if(kalan==0){
las=su[i][j].sc;
kalan=iki[mx-mx2];
}
kalan--;
if(kalan==0||j==0){
suf.pb({su[i][j].fr,las});
continue;
}
}
}
reverse(suf.begin(),suf.end());
//cerr<<left<<":"<<right<<" "<<mx<<endl;
while(v[mx].size()&&sor[v[mx].back()].fr>=left){
int ind=v[mx].back();
v[mx].pop_back();
//cerr<<sor[ind].fr<<"-"<<sor[ind].sc<<endl;
int l=0,r=pref.size()-1;
while(l<r){
int mi=(l+r+1)/2;
if(pref[mi].fr<=sor[ind].sc)l=mi;
else r=mi-1;
}
int son=l;
l=0;r=suf.size()-1;
while(l<r){
int mi=(l+r)/2;
if(suf[mi].sc>=sor[ind].fr)r=mi;
else l=mi+1;
}
int ilk=l;
int o=lower_bound(suf.begin(),suf.end(),suf[ilk])->fr;
l=0;r=pref.size()-1;
while(l<r){
int mi=(l+r)/2;
if(pref[mi].fr>=o)r=mi;
else l=mi+1;
}
int top=son-l;
l=0;r=suf.size()-1;
while(l<r){
int mi=(l+r)/2;
if(suf[mi].fr>=o)r=mi;
else l=mi+1;
}
top+=l-ilk+1;
ans[ind]=mx;
while(top>1){
ans[ind]++;
top=(top+1)/2;
}
}
return {pref,suf};
}
signed main(){
ios_base::sync_with_stdio(23^23);cin.tie(0);
cin>>n>>q;
iki[0]=1;
for(int i=1;i<=1000020;i++){
iki[i]=min(iki[i-1]*2,n);
}
for(int i=1;i<=n;i++){
cin>>arr[i];
}
for(int i=1;i<=q;i++){
cin>>sor[i].fr>>sor[i].sc;
}
lg[0]=-1;
for(int i=1;i<=n;i++){
table[i][0]=i;
lg[i]=lg[i/2]+1;
}
for(int i=1;i<19;i++){
for(int j=1;j<=n;j++){
table[j][i]=table[j][i-1];
if(j+(1<<(i-1))<=n){
if(arr[table[j][i]]<=arr[table[j+(1<<(i-1))][i-1]]){
table[j][i]=table[j+(1<<(i-1))][i-1];
}
}
}
}
for(int i=1;i<=q;i++){
v[arr[query(sor[i].fr,sor[i].sc)]].pb(i);
}
for(int i=0;i<=1e6;i++){
sort(v[i].begin(),v[i].end(),[&](const int &x,const int &y){
return sor[x].sc<sor[y].sc;
});
}
dfs(1,n);
for(int i=1;i<=q;i++){
cout<<ans[i]<<endl;
}
}
