/*
K stands for "Khongbietcode"
grade 11 computer science
Tran Dai Nghia Highschool for the gifted
*/
#include<bits/stdc++.h>
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long
#define pb push_back
#define ull unsigned long long
#define llll pair<ll,ll>
#define llllm map<ll,ll>
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b/gcd(a,b)
#define X first
#define Y second
#define INF 1LL<<60
using namespace std;
const int N=2e5+5;
int n,q,a[N],ft[N],l[N],r[N],L[N],R[N],question[N],ans[N],cur[N];
vector<pair<int,int>> query[N];
bool asked[N];
void update(int u)
{
while(u)
{
ft[u]++;
u-=u&(-u);
}
}
int get(int u)
{
int ret=0;
while(u<=2e5)
{
ret+=ft[u];
u+=u&(-u);
}
return ret;
}
void solve(){
cin >> n >> q;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
for(int i=1;i<=q;i++)
{
cin >> L[i] >> R[i];
query[L[i]-1].push_back({i,-1});
query[R[i]].push_back({i,1});
l[i]=1;r[i]=R[i]-L[i]+1;
ans[i]=1;
}
while(true)
{
bool check=false;
for(int i=1;i<=q;i++)
{
asked[i]=false;
cur[i]=0;
if(l[i]<=r[i])
{
check=true;
asked[i]=true;
int mid=(l[i]+r[i])/2;
question[i]=mid;
}
}
if(!check) break;
for(int i=1;i<=n;i++)
{
update(a[i]);
for(int j=0;j<query[i].size();j++)
{
int id=query[i][j].first,delta=query[i][j].second;
if(!asked[id]) continue;
cur[id]+=delta*get(question[id]);
if(delta==1)
{
if(cur[id]>=question[id])
{
ans[id]=question[id];
l[id]=question[id]+1;
}
else
{
r[id]=question[id]-1;
}
}
}
}
memset(ft,0,sizeof(ft));
}
for(int i=1;i<=q;i++)
{
cout << ans[i] << '\n';
}
}
int main(){
fastIO;
//freopen("tdk.inp","r",stdin);
//freopen("tdk.out","w",stdout);
//freopen("tdk.err","b",stderr);
int t=1;
//cin>>t;
while(t--){
solve();
cout << endl;
}
// cout << "\n" << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
return 0;
}
