#include<bits/stdc++.h>
using namespace std;
#define int long long
#define i128 int128
#define ii pair<int,int>
#define ld long double
#define vi vector<int>
#define vii vector<pair<int,int>>
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FOR1(i,a,b,c) for (int i=a;i<=b;i+=c)
#define REP(i,a,b) for (int i=a;i>=b;i--)
#define REP1(i,a,b,c) for(int i=b;i>=a;i-=c)
#define endh '\n';
#define len(a) a.length()
#define pb(c) push_back(c)
#define elif else if
#define ppb() pop_back()
#define rong std::npos
#define all(c) (c.begin(),c.end())
#define Z int
#define R double
#define lcm(a,b) ((int) (a/__gcd(a,b))*b)
#define mk(a,b) make_pair(a,b)
Z dx4[]={-1,1,0,0};
Z dy4[]={0,0,1,-1};
string co="YES",khong="NO";
const int mod=1e9+7;
const Z maxn=200005;
struct node
{
Z l,r,val;
node(){}
node(Z _val,Z _l,Z _r){
l=_l,r=_r,val=_val;}
}t[40*maxn];
Z n,q;
Z a[maxn],version[maxn];
Z cnode=0;
Z update(Z v,Z tl,Z tr,Z pos,Z nv)
{
if (tl==tr){
t[++cnode]=node(nv,0,0);
return cnode;
}
Z curr=++cnode;
Z tm=tl+tr>>1;
if (pos<=tm){
t[curr].l=update(t[v].l,tl,tm,pos,nv);
t[curr].r=t[v].r;
}
else{
t[curr].l=t[v].l;
t[curr].r=update(t[v].r,tm+1,tr,pos,nv);
}
t[curr].val=t[t[curr].l].val+t[t[curr].r].val;
return curr;
}
Z query(Z v,Z tl,Z tr,Z l,Z r)
{
if (tl>tr || l>r || tl>r || tr<l) return 0;
if (tl>=l && tr<=r) return t[v].val;
Z tm=tl+tr>>1;
return query(t[v].l,tl,tm,l,r)+query(t[v].r,tm+1,tr,l,r);
}
vi g[maxn];
void solve()
{
cin>>n>>q;
Z ma=0;
FOR(i,1,n){ cin>>a[i]; ma=max(ma,a[i]);}
FOR(i,1,n) g[a[i]+1].pb(i);
FOR(i,1,n) version[1]=update(version[1],1,n,i,1);
// FOR(i,1,ma) cout<<version[i]<<" "<<'?'<<'\n';
FOR(i,2,ma+1){
version[i]=version[i-1];
for (Z v:g[i]) version[i]=update(version[i],1,n,v,0);
}
while (q--){
Z l,r;
cin>>l>>r;
Z l1=1,r1=ma;
while (l1<=r1){
Z mid=l1+r1>>1;
if (query(version[mid],1,n,l,r)>=mid) l1=mid+1;
else r1=mid-1;
}
cout<<l1-1<<'\n';
}
// FOR(i,2,ma+1) cout<<query(version[i],1,n,1,n)<<'\n';
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
Z t=1;
// cin>>t;
while(t--) solve();
}
