#include <bits/stdc++.h>
using namespace std;
int n;
namespace SQRT_DS
{
int tole[100005], tori[100005];
int nxtle[100005], nxtri[100005];
const int BUC = 350;
void init()
{
for(int i=0;i<=n;i++)
{
tole[i] = tori[i] = 0;
nxtle[i] = -1;
nxtri[i] = n+1;
}
}
int when_added(int le, int ri)
{
le--;
return tole[le] + 1 + tori[ri];
}
void add(int le, int ri)
{
le--;
if(nxtri[le] > ri)
{
nxtri[le] = ri;
int cur = le;
while(nxtri[cur] <= n)
{
tole[nxtri[cur]] = max(tole[nxtri[cur]], tole[cur] + 1);
cur = nxtri[cur];
}
}
if(nxtle[ri] < le)
{
nxtle[ri] = le;
int cur = ri;
while(nxtle[cur] >= 0)
{
tori[nxtle[cur]] = max(tori[nxtle[cur]], tori[cur] + 1);
cur = nxtle[cur];
}
}
for(int i=1;i<=n;i++)
tole[i] = max(tole[i], tole[i-1]);
for(int i=n-1;i>=0;i--)
tori[i] = max(tori[i], tori[i+1]);
}
}
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;
}
/*
*/
