#include <bits/stdc++.h>
using namespace std ;
const int MAX = 2e5 + 10 ;
int arr[MAX] , L[MAX] , R[MAX] ;
int n , q ;
int cnt[MAX] , ans[MAX] ;
vector< pair<int , int> >vp(MAX) ;
vector<int>queries[MAX] ;
int bit[MAX] ;
void add(int i , int val)
{
for(; i < MAX ; i += (i & (-i)))
bit[i] += val ;
}
int get(int i)
{
int sum = 0 ;
for(; i > 0 ; i -= (i & (-i)))
sum += bit[i] ;
return sum ;
}
int query(int l , int r)
{
return (get(r) - get(l - 1)) ;
}
void init()
{
for(int i = 1 ; i <= n ; ++i)
queries[i].clear() ;
memset(bit , 0 , sizeof(bit)) ;
memset(cnt , 0 , sizeof(cnt)) ;
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n>>q ;
for(int i = 1 ; i <= n ; ++i)
cin>>arr[i] ;
for(int i = 1 ; i <= q ; ++i)
{
cin>>L[i]>>R[i] ;
vp[i] = {1 , n} ;
}
bool ok = false ;
while(!ok)
{
ok = true ;
init() ;
for(int i = 1 ; i <= q ; ++i)
{
if(vp[i].first > vp[i].second)
continue ;
ok = false ;
queries[L[i]-1].push_back(-i) ;
queries[R[i]].push_back(i) ;
}
for(int i = 1 ; i <= n ; ++i)
{
add(arr[i] , 1) ;
for(auto &j : queries[i])
{
int sgn = 1 ;
if(j < 0)
j *= -1 , sgn = -1 ;
cnt[j] += sgn * query((vp[j].first + vp[j].second) >> 1 , MAX-1) ;
}
}
for(int i = 1 ; i <= q ; ++i)
{
if(vp[i].first > vp[i].second)
continue ;
int x = (vp[i].first + vp[i].second) >> 1 ;
if(cnt[i] >= x)
ans[i] = x , vp[i].first = x+1 ;
else
vp[i].second = x-1 ;
}
}
for(int i = 1 ; i <= q ; ++i)
cout<<ans[i]<<"\n" ;
return 0 ;
}
