#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 2e5 + 2;
const int M = 2e5;;
int n, q, a[N];
struct Query
{
int l, k, pos;
};
vector<Query> ask[N];
struct Node
{
int left, right; // ID of left child & right child
int sum; // Max value of node
Node() {}
Node(int sum, int left, int right) : sum(sum), left(left), right(right) {}
} it[11000111]; // Each node has a position in this array, called ID
int nNode, ver[N];
inline void refine(int cur)
{
it[cur].sum = (it[it[cur].left].sum + it[it[cur].right].sum);
}
// Update a range, and return new ID of node
int update(int l, int r, int u, int oldId)
{
if (l == r)
{
it[nNode + 1] = Node(it[oldId].sum + 1, 0, 0);
++nNode;
return nNode;
}
int mid = (l + r) >> 1;
int cur = ++nNode;
if (u <= mid)
{
it[cur].left = update(l, mid, u, it[oldId].left);
it[cur].right = it[oldId].right;
refine(cur);
}
else
{
it[cur].left = it[oldId].left;
it[cur].right = update(mid + 1, r, u, it[oldId].right);
refine(cur);
}
return cur;
}
int get(int nodeId, int l, int r, int u, int v)
{
if (nodeId == 0)
return 0;
if (v < l || r < u)
return 0;
if (u <= l && r <= v)
return it[nodeId].sum;
int mid = (l + r) >> 1;
return (get(it[nodeId].left, l, mid, u, v) + get(it[nodeId].right, mid + 1, r, u, v));
}
int main()
{
// freopen(task ".inp", "r", stdin);
// freopen(task ".out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
ver[i] = update(1, M, a[i], ver[i - 1]);
for (int i = 1; i <= q; i++)
{
int l, r;
cin >> l >> r;
int low = 1, high = n, mid, tmp = 0;
while (low <= high)
{
mid = (low + high) / 2;
if (get(ver[r], 1, M, mid, M) - get(ver[l - 1], 1, M, mid, M) >= mid)
{
tmp = mid;
low = mid + 1;
}
else
high = mid - 1;
}
cout << tmp << '\n';
}
return 0;
}
