#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);
if(st != dr)
aint[nod] = max(aint[nod*2], aint[nod*2+1]);
else
aint[nod] = 0;
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;
vector<int> changed;
int old[2][100005];
struct MINI_BRUT
{
int val, c;
set<pair<int,int>> all;
vector<pair<int,int>> 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;
for(auto it:all)
if(x.first <= it.first && it.first < x.second)
poz = max(poz, it.first);
return poz;
}
void brut_calc()
{
iset.clear();
pair<int,int> cur = {-1,-1};
while(1)
{
cur = find_next(cur);
if(cur.second == n+1)
break;
iset.push_back(cur);
}
}
void init(int copval, int copc, vector<pair<int,int>> idk)
{
val = copval;
c = copc;
all.clear();
for(auto x:idk)
{
assert(x.first < x.second);
all.insert(x);
}
brut_calc();
}
void add(int le, int ri)
{
assert(le < ri);
if(all.find({le,ri}) != all.end())
return;
all.insert({le,ri});
int poz = lower_bound(iset.begin(), iset.end(), make_pair(ri,0)) - iset.begin() - 1;
assert(poz >= 0);
if(ri < iset[poz].second && (poz == 0 || iset[poz-1].second <= le))
{
/*brut_calc();
assert(iset[poz] == make_pair(le,ri));
return;*/
pair<int,int> cur = {le,ri};
for(int i=poz;i<iset.size();i++)
{
assert(cur.second != n+1);
if(iset[i] == cur)
break;
if(c == 0) changed.push_back(i);
else changed.push_back((int)iset.size() - 1 - i);
old[c][i] = iset[i].second;
iset[i] = cur;
cur = find_next(cur);
}
}
}
};
struct BRUT_DS
{
MINI_BRUT ds[2];
int val;
void init(int copval, vector<pair<int,int>> idk)
{
val = copval;
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);
assert(ds[0].iset.size() == ds[1].iset.size());
int lun = ds[0].iset.size();
for(int i=0;i<lun;i++)
seg_ds.baga(n - ds[1].iset[lun-1 - i].second, ds[0].iset[i].second - 1, val);
}
void add(int le, int ri)
{
/*int lun = ds[0].iset.size();
for(int i=0;i<lun;i++)
seg_ds.scoate(n - ds[1].iset[lun-1 - i].second, ds[0].iset[i].second - 1, val);
changed.clear();
ds[0].add(le, ri);
ds[1].add(n-ri, n-le);
for(int i=0;i<lun;i++)
seg_ds.baga(n - ds[1].iset[lun-1 - i].second, ds[0].iset[i].second - 1, val);*/
changed.clear();
ds[0].add(le, ri);
ds[1].add(n-ri, n-le);
int lun = ds[0].iset.size();
for(int i:changed)
{
seg_ds.scoate(n - old[1][lun-1 - i], old[0][i] - 1, val);
seg_ds.baga(n - ds[1].iset[lun-1 - i].second, ds[0].iset[i].second - 1, val);
}
}
}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;
}
seg_ds.build(1,0,n);
int unde = n;
SQRT_DS::init();
for(int i=1;i<=m;i++)
{
int maxc = seg_ds.query(v[i].first, v[i].second - 1);
//cerr<<"P 2\n";
//cerr<<v[i].first<<" "<<v[i].second<<" zzz\n";
if(maxc == 0)//add i to unde
{
//cerr<<"incepe sqrt\n";
while(unde >= 1 && 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 >= 1);
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;
}
/*
*/
