#include<bits/stdc++.h>
using namespace std ;
#define ff first
#define ss second
#define int long long
typedef long long ll ;
typedef pair<int,int> pii ;
const int maxn = 2e5+12;
const int maxk = 110 ;
const int maxlg = 25 ;
const int sq = 320 ;
const int MOD = 998244353;
const int INF = 1e17 ;
int n,q,cnt[maxn],a[maxn],h,uph,ans[maxn] ;
struct qee{
int l,r,num ;
}qe[maxn] ;
bool cmp(qee A , qee B){
if(A.l/sq==B.l/sq){
if((A.l/sq)&1)
return A.r>B.r ;
return A.r<B.r ;
}
return A.l<B.l ;
}
void solve(){
cin>>n>>q ;
for(int i=1 ; i<=n ; i++)
cin>>a[i] ;
for(int i=1 ; i<=q ;i++){
cin>>qe[i].l>>qe[i].r ;
qe[i].num=i ;
}
sort(qe,qe+q+1,cmp) ;
int l=1 , r=1 ;
cnt[a[1]]++ ;
h=1 ; uph=1 ;
for(int i=1 ; i<=q ; i++){
while(r<qe[i].r){
r++ ;
cnt[a[r]]++ ;
if(a[r]>=h) uph++ ;
if(uph-cnt[h]>=h+1){
uph-=cnt[h] ; h++ ;
}
}
while(qe[i].l<l){
l-- ;
cnt[a[l]]++ ;
if(a[l]>=h) uph++ ;
if(uph-cnt[h]>=h+1){
uph-=cnt[h] ; h++ ;
}
}
while(r>qe[i].r){
cnt[a[r]]-- ;
if(a[r]>=h) uph-- ;
if(uph<h){
uph+=cnt[h-1] ; h-- ;
}
r-- ;
}
while(l<qe[i].l){
cnt[a[l]]-- ;
if(a[l]>=h) uph-- ;
if(uph<h){
uph+=cnt[h-1] ; h-- ;
}
l++ ;
}
ans[qe[i].num]=h ;
}
for(int i=1 ; i<=q ; i++)
cout<<ans[i]<<'\n' ;
}
signed main(){
ios::sync_with_stdio(0) ;
cin.tie(0) ; cout.tie(0) ;
solve() ;
}
