#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
const int tree_siz = 1024*256-1;
pii min_[tree_siz+1];
int minL[tree_siz+1];
pii get_min(int akt, int p1, int p2, int s1, int s2)
{
if(p2 < s1 || p1 > s2) return {(int)1e9,-1};
if(p1 >= s1 && p2 <= s2) return min_[akt];
return min(get_min(akt*2,p1,(p1+p2)/2,s1,s2),get_min(akt*2+1,(p1+p2)/2+1,p2,s1,s2));
}
void upd(int v)
{
min_[v] = min(min_[v*2],min_[v*2+1]);
if(v != 1) upd(v/2);
}
void change(int v, pii val)
{
min_[tree_siz/2+1+v] = val;
upd((tree_siz/2+1+v)/2);
}
ll get_minL(int akt, int p1, int p2, int s1, int s2)
{
if(p2 < s1 || p1 > s2) return 1e9;
if(p1 >= s1 && p2 <= s2) return minL[akt];
return min(get_minL(akt*2,p1,(p1+p2)/2,s1,s2),get_minL(akt*2+1,(p1+p2)/2+1,p2,s1,s2));
}
void upd2(int v)
{
minL[v] = min(minL[v*2],minL[v*2+1]);
if(v != 1) upd2(v/2);
}
void changeL(int v, int val)
{
minL[tree_siz/2+1+v] = val;
upd2((tree_siz/2+1+v)/2);
}
set<pii> mins[100001];
set<int> minsL[100001];
void upd_seg(int a, bool is);
int answer[100001];
int Acnt[100001];
vector<pii> segs;
vector<pii> segs2;
set<int> active;
vector<pii> cur_segs;
set<pii> L_segs[100001];
set<pii> R_segs[100001];
priority_queue<pii,vector<pii>,greater<pii>> pq;
int A;
bool is_cross(pii a, pii b)
{
if(a > b) swap(a,b);
if(a.ss < b.ff) return 0;
return 1;
}
void set_elm(int v, int a)
{
mins[segs[v].ss].erase({segs[v].ff,v});
if(siz(mins[segs[v].ss]) == 0) change(segs[v].ss,{(int)1e9,-1});
else change(segs[v].ss,*mins[segs[v].ss].begin());
minsL[segs[v].ff].erase(v);
if(siz(minsL[segs[v].ff]) == 0) changeL(segs[v].ff,1e9);
else changeL(segs[v].ff,*minsL[segs[v].ff].begin());
if(segs[v].ff != segs[v].ss)
{
minsL[segs[v].ss].erase(v);
if(siz(minsL[segs[v].ss]) == 0) changeL(segs[v].ss,1e9);
else changeL(segs[v].ss,*minsL[segs[v].ss].begin());
}
answer[v] = a;
active.erase(v);
}
int check_pref(int pref, bool is = 0)
{
segs2 = {};
int cnt = 0;
forall(it,active)
{
segs2.pb({segs[it].ss,segs[it].ff});
cnt++;
if(cnt == pref) break;
}
sort(all(segs2));
int ans = 0;
int prev_end = -1e9;
forall(it,segs2)
{
if(it.ss > prev_end)
{
if(is) cur_segs.pb({it.ss,it.ff});
ans++;
prev_end = it.ff;
}
}
return ans;
}
void repair_seg(int v)
{
//L
bool was_L = 0;
while(siz(L_segs[v]) > 0)
{
auto L = L_segs[v].begin();
if((*L).ff >= cur_segs[v].ff) break;
int l2 = segs[(*L).ss].ff;
if(cur_segs[v-1].ss >= l2)
{
was_L = 1;
cur_segs[v-1].ff = max(cur_segs[v-1].ff,l2);
}
L_segs[v].erase(L);
}
if(was_L) upd_seg(v-1,1);
//R
bool was_R = 0;
while(siz(R_segs[v]) > 0)
{
auto R = --R_segs[v].end();
if((*R).ff <= cur_segs[v].ss) break;
int r2 = segs[(*R).ss].ss;
if(cur_segs[v+1].ff <= r2)
{
was_R = 1;
cur_segs[v+1].ss = min(cur_segs[v+1].ss,r2);
}
R_segs[v].erase(R);
}
if(was_R) upd_seg(v+1,1);
}
void upd_seg(int v, bool is)
{
if(is) repair_seg(v);
while(true)
{
pii m = get_min(1,0,tree_siz/2,cur_segs[v].ss,tree_siz/2);
if(m.ss == -1 || m.ff > cur_segs[v].ff) break;
set_elm(m.ss,A);
}
int f = get_minL(1,0,tree_siz/2,cur_segs[v].ff,cur_segs[v].ss);
int f2 = 1e9;
forall(it,active)
{
if(is_cross(cur_segs[v],segs[it]))
{
f2 = it;
break;
}
}
if(f == 1e9) return;
pq.push({f,v});
}
void solve(int A2,int k)
{
if(k == 0) return;
A = A2;
int l = 1;
int r = siz(active);
int cur_ptr = 1;
int ans = 1;
while(cur_ptr <= r)
{
int ptr2 = cur_ptr*2;
if(check_pref(min(r,ptr2)) <= k)
{
cur_ptr = ptr2;
ans = cur_ptr;
}
else break;
}
ans = min(ans,r);
if(ans != r)
{
int add = cur_ptr/2;
while(add != 0)
{
int ptr2 = cur_ptr+add;
if(check_pref(ptr2) <= k)
{
cur_ptr = ptr2;
ans = cur_ptr;
}
add /= 2;
}
}
cur_segs = {};
check_pref(ans,1);
rep(i,siz(cur_segs))
{
L_segs[i] = {};
R_segs[i] = {};
}
pq = {};
rep(i,siz(cur_segs)) upd_seg(i,0);
while(!pq.empty())
{
pii t = pq.top();
pq.pop();
if(answer[t.ff] != -1 || !is_cross(segs[t.ff],cur_segs[t.ss]))
{
upd_seg(t.ss,1);
continue;
}
set_elm(t.ff,A);
bool was = 0;
if(t.ss != 0 && is_cross(segs[t.ff],cur_segs[t.ss-1]))
{
was = 1;
L_segs[t.ss].insert({segs[t.ff].ss,t.ff});
R_segs[t.ss-1].insert({segs[t.ff].ff,t.ff});
}
if(t.ss != siz(cur_segs)-1 && is_cross(segs[t.ff],cur_segs[t.ss+1]))
{
was = 1;
R_segs[t.ss].insert({segs[t.ff].ff,t.ff});
L_segs[t.ss+1].insert({segs[t.ff].ss,t.ff});
}
if(!was)
{
cur_segs[t.ss].ff = max(cur_segs[t.ss].ff,segs[t.ff].ff);
cur_segs[t.ss].ss = min(cur_segs[t.ss].ss,segs[t.ff].ss);
}
upd_seg(t.ss,1);
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random_start();
int n,m;
cin >> n >> m;
rep(i,n)
{
int a;
cin >> a;
Acnt[a]++;
}
rep(i,m)
{
int l,r;
cin >> l >> r;
mins[r].insert({l,i});
minsL[r].insert(i);
minsL[l].insert(i);
active.insert(i);
segs.pb({l,r});
answer[i] = -1;
}
rep(i,tree_siz+1)
{
min_[i] = {1e9,-1};
minL[i] = 1e9;
}
rep2(i,1,n) if(siz(mins[i]) != 0) change(i,*mins[i].begin());
rep2(i,1,n) if(siz(minsL[i]) != 0) changeL(i,*minsL[i].begin());
for(int i = n; i >= 1; i--) solve(i,Acnt[i]);
rep(i,m) cout << answer[i] << "\n";
}
