#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 1;
struct Node {
int val,Lid,Rid;
Node() {};
Node(int val, int L, int R): val(val), Lid(L), Rid(R) {}
} t[21*maxn];
int n,Q, root[maxn + 1], nNode = 0, version = 0;
int build(int tl, int tr) {
int cur = ++nNode;
if (tl == tr) t[cur] = Node(0,0,0);
else {
int tm = (tl + tr)/2;
t[cur].val = 0;
t[cur].Lid = build(tl,tm);
t[cur].Rid = build(tm+1,tr);
}
return cur;
}
int update(int oldID, int tl, int tr, int pos) {
if (tl == tr) {
++nNode;
t[nNode] = Node(t[oldID].val + 1,0,0);
return nNode;
}
int tm = (tl + tr)/2;
int cur = ++nNode;
// assert(cur < 11*maxn);
if (pos <= tm) {
t[cur].Lid = update(t[oldID].Lid,tl,tm,pos);
t[cur].Rid = t[oldID].Rid;
t[cur].val = t[t[cur].Lid].val + t[t[cur].Rid].val;
} else {
t[cur].Rid = update(t[oldID].Rid,tm+1,tr,pos);
t[cur].Lid = t[oldID].Lid;
t[cur].val = t[t[cur].Lid].val + t[t[cur].Rid].val;
}
return cur;
}
int get(int cur, int tl, int tr, int l, int r) {
if (tl > r || tr < l) return 0;
if (tl >= l && tr <= r) return t[cur].val;
int tm = (tl + tr)/2;
return get(t[cur].Lid,tl,tm,l,r) + get(t[cur].Rid,tm+1,tr,l,r);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> Q;
root[0] = build(1,maxn - 1);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
++version;
root[version] = update(root[version-1],1,maxn-1,x);
}
// cout << nNode << '\n';
while (Q--) {
int l,r;
cin >> l >> r;
int res = 0, L = 1, R = r - l + 1;
while (L <= R) {
int mid = (L + R)/2;
if (get(root[r],1,maxn-1,mid,maxn-1) - get(root[l-1],1,maxn-1,mid,maxn-1) >= mid) {
res = mid;
L = mid+1;
} else R = mid-1;
}
printf("%d\n",res);
}
return 0;
}
