#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
using namespace std;
const int maxn = 2e5 + 10;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct persistent_sgt
{
struct node
{
int lt, rt, val;
node(int _lt, int _rt, int _val)
{
lt = _lt;
rt = _rt;
val = _val;
}
};
vector < node > t;
int tmr, n;
int build(int l, int r, vector < int > a)
{
if(l == r)
{
t.pb(node(-1, -1, a[l]));
return tmr ++;
}
int mid = (l + r)/2;
int onl = build(l, mid, a);
int onr = build(mid+1, r, a);
t.pb(node(onl, onr, a[l]));
return tmr ++;
}
int do_build(int sz, vector < int > a)
{
tmr = 0;
n = sz;
return build(1, n, a);
}
int update(int i, int l, int r, int upd_pos, int upd_val)
{
if(l == r)
{
t.pb(node(-1, -1, upd_val));
return tmr ++;
}
int mid = (l + r)/2;
int onl = t[i].lt, onr = t[i].rt;
if(upd_pos <= mid)onl = update(t[i].lt, l, mid, upd_pos, upd_val);
else onr = update(t[i].rt, mid+1, r, upd_pos, upd_val);
t.pb(node(onl, onr, t[onl].val + t[onr].val));
return tmr ++;
}
int do_update(int root, int upd_pos, int upd_val)
{
return update(root, 1, n, upd_pos, upd_val);
}
int query(int i, int l, int r, int ql, int qr)
{
if(i == -1)return 0;
if(qr < l || ql > r)return 0;
if(ql <= l && r <= qr)return t[i].val;
int mid = (l + r)/2;
return query(t[i].lt, l, mid, ql, qr) + query(t[i].rt, mid+1, r, ql, qr);
}
int do_query(int root, int ql, int qr)
{
return query(root, 1, n, ql, qr);
}
};
persistent_sgt s;
int n, q;
int p[maxn];
vector < int > pos[maxn];
int total, root[maxn], dp[maxn], mp[maxn], is_mp[maxn];
int main()
{
speed();
cin >> n >> q;
vector < int > v;
vector < int > init;
for (int i = 1; i <= n; ++ i)
{
cin >> p[i];
init.pb(0);
if(pos[p[i]].size() == 0)v.pb(p[i]);
pos[p[i]].pb(i);
}
init.pb(0);
total = v.size();
sort(v.begin(), v.end());
int last_root = s.do_build(n, init);
/// shte sme na posledniq
for (int i = v.size()-1; i >= 0; -- i)
{
int x = v[i];
mp[x] = i;
is_mp[x] = 1;
for (auto index: pos[x])
{
int curr_root = s.do_update(last_root, index, 1);
last_root = curr_root;
}
root[i] = last_root;
}
int ptr = -1;
for(int i = 200000; i>= 0; -- i)
{
if(is_mp[i])ptr = mp[i];
dp[i] = ptr;
}
while(q --)
{
int ql, qr;
cin >> ql >> qr;
int l = 0, r = 200000, mid, ans = 0;
while(l <= r)
{
mid = (l + r)/2;
int sum = 0;
if(dp[mid] != -1)sum = s.do_query(root[dp[mid]], ql, qr);
if(sum >= mid)
{
l = mid + 1;
ans = mid;
}
else r = mid - 1;
}
cout << ans << endl;
}
return 0;
}
