///0-0 : what is your motivation, quan606303?
///quan606303 : Hutao
/*idea :
*/
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout);
using namespace std;
const int MOD=1e9+7;
const int maxn=200005;
int BIT[maxn];
int n,q;
pair<int,int> a[maxn];
void upd(int x,int cnt)
{
for (;x<maxn;x+=(x&-x))BIT[x]+=cnt;
}
int get(int x)
{
int sum=0;
for (;x>0;x&=(x-1))sum+=BIT[x];
return sum;
}
int get_range(int l,int r)
{
return get(r)-get(l-1);
}
int l[maxn],r[maxn],ans[maxn];
pair<int,int> b[maxn];
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for (int i=1;i<=n;i++)
{
cin>>a[i].fi;
a[i].se=i;
}
sort(a+1,a+1+n);
for (int i=1;i<=q;i++)
{
cin>>b[i].fi>>b[i].se;
l[i]=1;
r[i]=n;
ans[i]=0;
}
vector<vector<int> > queries;
bool process=true;
while (process)
{
process=false;
queries.assign(n+5,vector<int>());
for (int i=1;i<=q;i++)
{
if (l[i]>r[i])continue;
process=true;
int mid=(l[i]+r[i])/2;
queries[mid].push_back(i);
}
vector<int> vt;
for (int mid=n,i=n;mid>=1;mid--)
{
while (i>=1&&a[i].fi>=mid)
{
upd(a[i].se,1);
vt.push_back(a[i].se);
i--;
}
int cnt=get_range(b[mid].fi,b[mid].se);
for (auto c:queries[mid])
{
int cnt=get_range(b[c].fi,b[c].se);
if (cnt>=mid)
{
l[c]=mid+1;
ans[c]=mid;
}
else r[c]=mid-1;
}
}
for (auto i:vt)upd(i,-1);
queries.clear();
}
for (int i=1;i<=q;i++)cout<<ans[i]<<endl;
return 0;
}
