#include <bits/stdc++.h>
using namespace std;
int n;
struct MINI_DS
{
const int BUC = 300;
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] = n+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 calc_big(int le)
{
int cur = le, cnt = 0;
while(cur/BUC == le/BUC && cur <= n)
{
cur = tori[cur];
cnt++;
}
big_tori[le] = {cur, cnt};
}
void add(int le, int ri)
{
assert(le < ri);
propagate(le / BUC);
if(tori[le] <= ri)
return;
tori[le] = ri;
calc_big(le);
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
{
calc_big(i);
}
}
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
{
calc_big(i);
}
}
}
}
}
}
};
namespace SQRT_DS
{
MINI_DS ds[2];
vector<pair<int,int>> idk;
void init()
{
idk.clear();
ds[0].init();
ds[1].init();
}
int when_added(int le, int ri)
{
return ds[1].cntri(n - le) + 1 + ds[0].cntri(ri);
}
void add(int le, int ri)
{
ds[0].add(le, ri);
ds[1].add(n - ri, n - le);
idk.push_back({le, ri});
}
}
struct SEGTREE
{
set<int> idk[400005];
set<int> vals[400005];
int aint[400005];
void build(int nod, int st, int dr)
{
vals[nod].clear();
aint[nod] = 0;
if(st == dr)
return;
int mij = (st + dr) / 2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
}
void bg(int nod, int st, int dr, int le, int ri, int newv)
{
if(le > ri)
return;
if(le == st && dr == ri)
{
vals[nod].insert(newv);
aint[nod] = max(aint[nod], newv);
return;
}
int mij = (st + dr) / 2;
bg(nod*2, st, mij, le, min(mij,ri), newv);
bg(nod*2+1, mij+1, dr, max(mij+1,le), ri, newv);
aint[nod] = max(aint[nod*2], aint[nod*2+1]);
if(!vals[nod].empty()) aint[nod] = max(aint[nod], *vals[nod].rbegin());
}
void baga(int le, int ri, int newv)
{
//bg(1,0,n,le,ri,newv);
for(int i=le;i<=ri;i++)
idk[i].insert(newv);
}
void sc(int nod, int st, int dr, int le, int ri, int newv)
{
if(le > ri)
return;
if(le == st && dr == ri)
{
vals[nod].erase(newv);
aint[nod] = max(aint[nod*2], aint[nod*2+1]);
if(!vals[nod].empty()) aint[nod] = max(aint[nod], *vals[nod].rbegin());
return;
}
int mij = (st + dr) / 2;
sc(nod*2, st, mij, le, min(mij,ri), newv);
sc(nod*2+1, mij+1, dr, max(mij+1,le), ri, newv);
aint[nod] = max(aint[nod*2], aint[nod*2+1]);
if(!vals[nod].empty()) aint[nod] = max(aint[nod], *vals[nod].rbegin());
}
void scoate(int le, int ri, int newv)
{
//sc(1,0,n,le,ri,newv);
for(int i=le;i<=ri;i++)
idk[i].erase(newv);
}
int qry(int nod, int st, int dr, int le, int ri)
{
if(le > ri)
return 0;
if(le == st && dr == ri)
return aint[nod];
int mij = (st + dr) / 2;
int aux = max(qry(nod*2, st, mij, le, min(mij,ri)), qry(nod*2+1, mij+1, dr, max(mij+1,le), ri));
if(!vals[nod].empty()) aux = max(aux, *vals[nod].rbegin());
return aux;
}
int query(int le, int ri)
{
int mxm = 0;
for(int i=le;i<=ri;i++)
if(!idk[i].empty())
mxm = max(mxm, *idk[i].rbegin());
return mxm;
//return qry(1,0,n,le,ri);
}
}seg_ds[2];
struct MINI_BRUT
{
int val, c;
set<pair<int,int>> all, iset;
pair<int,int> find_next(pair<int,int> x)
{
pair<int,int> best = {x.second, n+1};
for(auto it:all)
{
if(it.first >= x.second && it.second < best.second)
{
best = it;
}
}
return best;
}
int find_worst(pair<int,int> x)
{
int poz = x.first + 1;
for(auto it:all)
if(x.first <= it.first && it.first < x.second)
poz = max(poz, it.first + 1);
return poz;
}
map<pair<int,int>,bool> starts_here;
vector<pair<int,int>> upds;
void brut_calc()
{
for(auto [le,ri]:upds)
seg_ds[c].scoate(le, ri, val);
upds.clear();
pair<int,int> cur = {-1,-1};
while(1)
{
cur = find_next(cur);
if(cur.second == n+1)
break;
upds.push_back({find_worst(cur), cur.second - 1});
}
for(auto [le,ri]:upds)
seg_ds[c].baga(le, ri, val);
}
void init(int copval, int copc, vector<pair<int,int>> idk)
{
val = copval;
c = copc;
upds.clear();
all.clear();
for(auto x:idk)
{
assert(x.first < x.second);
all.insert(x);
}
brut_calc();
}
void add(int le, int ri)
{
if(all.find({le,ri}) != all.end())
return;
all.insert({le,ri});
brut_calc();
}
};
struct BRUT_DS
{
MINI_BRUT ds[2];
void init(int val, vector<pair<int,int>> idk)
{
ds[0].init(val, 0, idk);
for(auto&x:idk)
{
x.first = n - x.first;
x.second = n - x.second;
swap(x.first, x.second);
}
ds[1].init(val, 1, idk);
}
void add(int le, int ri)
{
ds[0].add(le, ri);
ds[1].add(n-ri, n-le);
}
}simple[100005];
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;
v[i].first--;
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);
}
}
}*/
seg_ds[0].build(1,0,n);
seg_ds[1].build(1,0,n);
int unde = n;
SQRT_DS::init();
for(int i=1;i<=m;i++)
{
int maxc = max(seg_ds[0].query(v[i].first, v[i].second), seg_ds[1].query(n-v[i].second, n-v[i].first));
//cerr<<"P 2\n";
if(maxc == 0)//add i to unde
{
//cerr<<"incepe sqrt\n";
while(unde >= 0 && SQRT_DS::when_added(v[i].first, v[i].second) > fr[unde])
{
//cerr<<unde<<": "<<SQRT_DS::when_added(v[i].first, v[i].second)<<" vs "<<fr[unde]<<"\n";
if(fr[unde] > 0) simple[unde].init(unde, SQRT_DS::idk);
unde--;
SQRT_DS::init();
}
assert(unde >= 0);
SQRT_DS::add(v[i].first, v[i].second);
rez[i] = unde;
//cerr<<"final unde: "<<unde<<"\n";
//cerr<<"termina sqrt\n";
}
else//add i to maxc
{
//cerr<<"incepe simple\n";
rez[i] = maxc;
simple[maxc].add(v[i].first, v[i].second);
//cerr<<"termina simple\n";
}
//cerr<<"P 3\n";
}
for(int i=1;i<=m;i++)
{
assert(rez[i] != -1);
cout<<rez[i]<<"\n";
}
return 0;
}
/*
*/
