#include <bits/stdc++.h>
#define SPED \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen
const lint INF = 0x1f1f1f1f1f1f1f1f;
const lint NEG = 0xE1E1E1E1E1E1E1E1;
using namespace std;
int n, q, idx[200005], nodes, ver[200005];
lint a[200005];
vector<int> adj[200005];
lint seg[22 * 200005], L[22 * 200005], R[22 * 200005];
int build(int l, int r)
{
int cur = ++nodes;
if (l == r)
{
seg[cur] = 0;
return cur;
}
int mid = l + r >> 1;
L[cur] = build(l, mid);
R[cur] = build(mid + 1, r);
return cur;
}
int update(int prev, int l, int r, int idx, int k)
{
int cur = ++nodes;
if (l == r)
{
seg[cur] = seg[prev] + k;
return cur;
}
int mid = l + r >> 1;
L[cur] = L[prev];
R[cur] = R[prev];
if (idx <= mid)
L[cur] = update(L[prev], l, mid, idx, k);
else
R[cur] = update(R[prev], mid + 1, r, idx, k);
seg[cur] = seg[L[cur]] + seg[R[cur]];
return cur;
}
lint get(int nodel, int noder, int l, int r, int templ, int tempr)
{
if (templ <= l and r <= tempr)
return seg[noder] - seg[nodel];
else if (r < templ or tempr < l)
return 0;
int mid = l + r >> 1;
return get(L[nodel], L[noder], l, mid, templ, tempr) + get(R[nodel], R[noder], mid + 1, r, templ, tempr);
}
lint binaryu(int L, int R) // chặt nhị phân tìm chỉ số H lớn nhất
{
int l = 1, r = R - L + 1, mid, ans = 0;
while (l <= r)
{
mid = l + r >> 1;
if (get(ver[L - 1], ver[R], 1, 200000, mid, 200000) >= mid)
{
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
return ans;
}
fami lore()
{
SPED;
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
// seg[0] = build(1, 200000);
for (int i = 1; i <= n; i++)
ver[i] = update(ver[i - 1], 1, 200000, a[i], 1);
while (q--)
{
int l, r;
cin >> l >> r;
cout << binaryu(l, r) << endl;
}
}
// Let your soul wander where dreams are born.
