#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
struct node
{
int su=0, s, e, lc, rc;
};
const int M = 2e5 + 3;
int rt[M], tot=1;
vector<node> seg;
vector<int> ind[M];
void add()
{
node a;seg.push_back(a);
}
void modify(int p,int v)
{
if (seg[v].s+1==seg[v].e)
{
seg[v].su=1;
return;
}
int mid=(seg[v].s+seg[v].e)/2;
if (p<mid)
add(), seg[tot]=seg[seg[v].lc], seg[v].lc=tot, modify(p,tot++);
else
add(), seg[tot]=seg[seg[v].rc], seg[v].rc=tot, modify(p,tot++);
seg[v].su=seg[seg[v].lc].su+seg[seg[v].rc].su;
}
int get(int l,int r,int v)
{
if (l>=seg[v].e or r<=seg[v].s) return 0;
if (l<=seg[v].s && seg[v].e<=r) return seg[v].su;
return get(l,r,seg[v].lc)+get(l,r,seg[v].rc);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(NULL), cout.tie(NULL);
int n,qr;
cin>>n>>qr;
int a[n];
for (int i=0;i<n;i++)
cin>>a[i], ind[a[i]].push_back(i);
add(), rt[M-2]=0, seg[0].s=0, seg[0].e=n;
queue<int> q;
q.push(0);
while (!q.empty())
{
int x=q.front();q.pop();
if (seg[x].s+1==seg[x].e) continue;
int mid=(seg[x].s+seg[x].e)/2;
add(), seg[x].lc=tot, seg[tot].s=seg[x].s, seg[tot++].e=mid;
add(), seg[x].rc=tot, seg[tot].s=mid, seg[tot++].e=seg[x].e;
q.push(seg[x].lc), q.push(seg[x].rc);
}
for (int i=M-3;i>0;i--)
{
add(), rt[i]=tot, seg[tot++]=seg[rt[i+1]];
for (int x:ind[i])
modify(x,rt[i]);
}
while (qr--)
{
int l, r;
cin>>l>>r;l--;
int s=1, e=M;
while (s+1<e)
{
int mid=(s+e)/2;
if (get(l,r,rt[mid])>=mid)
s=mid;
else
e=mid;
}
cout<<s<<endl;
}
return 0;
}
