#include <bits/stdc++.h>
using namespace std;
int n;
struct MINI_DS
{
const int BUC = 20;
int tori[100005];
pair<int,int> big_tori[100005];//{poz, cnt}
int lazy_assign[100005];
void init()
{
for(int i=0;i<=(n+1)/BUC;i++)
lazy_assign[i] = 0;
for(int i=0;i<=n;i++)
{
tori[i] = n+1;
big_tori[i] = {n+1, 1};
}
}
int cntri(int x)
{
int cnt = 0;
while(x <= n)
{
if(lazy_assign[x/BUC])
{
cnt++;
x = lazy_assign[x/BUC];
}
else
{
cnt += big_tori[x].second;
x = big_tori[x].first;
/*cnt++;
x = tori[x];*/
}
}
return cnt - 1;
}
void propagate(int b)
{
if(!lazy_assign[b])
return;
for(int i=b*BUC;i<min(n+1, (b+1)*BUC);i++)
{
tori[i] = lazy_assign[b];
big_tori[i] = {lazy_assign[b], 1};
}
lazy_assign[b] = 0;
}
void add(int le, int ri)
{
assert(le < ri);
propagate(le / BUC);
if(tori[le] <= ri)
return;
tori[le] = ri;
int cur = le, cnt = 0;
while(cur/BUC == le/BUC && cur <= n)
{
cur = tori[cur];
cnt++;
}
big_tori[le] = {cur, cnt};
big_tori[le] = {ri, 1};
for(int i=le-1;i>=0 && i/BUC == le/BUC;i--)
{
if(tori[i] > ri)
{
tori[i] = ri;
big_tori[i] = big_tori[le];
}
else
break;
}
for(int b = le/BUC - 1; b>=0; b--)
{
if(lazy_assign[b])
{
if(ri < lazy_assign[b])
lazy_assign[b] = ri;
}
else
{
if(ri < tori[b*BUC])
{
lazy_assign[b] = ri;
}
else if(ri < tori[(b+1)*BUC - 1])
{
for(int i=(b+1)*BUC-1;i>=b*BUC;i--)
{
if(ri < tori[i])
{
tori[i] = ri;
big_tori[i] = {ri, 1};
}
else
break;
}
}
}
}
}
};
namespace SQRT_DS
{
MINI_DS ds[2];
void init()
{
ds[0].init();
ds[1].init();
}
int when_added(int le, int ri)
{
le--;
return ds[1].cntri(n - le) + 1 + ds[0].cntri(ri);
}
void add(int le, int ri)
{
le--;
ds[0].add(le, ri);
ds[1].add(n - ri, n - le);
}
}
int m;
int fr[100005];
pair<int,int> v[100005];
int rez[100005];
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m;
int a;
for(int i=1;i<=n;i++)
{
cin>>a;
fr[a]++;
}
for(int i=1;i<=m;i++)
{
cin>>v[i].first>>v[i].second;
rez[i] = -1;
}
for(int val=n;val>=1;val--)
{
if(fr[val] == 0)
continue;
SQRT_DS::init();
for(int i=1;i<=m;i++)
{
if(rez[i] != -1)
continue;
if(SQRT_DS::when_added(v[i].first, v[i].second) <= fr[val])
{
rez[i] = val;
SQRT_DS::add(v[i].first, v[i].second);
}
}
}
for(int i=1;i<=m;i++)
{
assert(rez[i] != -1);
cout<<rez[i]<<"\n";
}
return 0;
}
/*
*/
