#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
const int maxP = 200000;
int cnt = 0;
struct Node {
int l, r;
int sum;
Node(int left, int right, int v) : l(left), r(right), sum(v) {};
Node() : l(0), r(0), sum(0) {};
};
Node nnode[36 * maxP];
struct SegTree {
int sz = 0;
int createTree(int l, int r) {
if (l == r) {
return cnt++;
}
int m = (l + r) >> 1;
int nd1 = createTree(l, m);
int nd2 = createTree(m + 1, r);
nnode[cnt].l = nd1;
nnode[cnt].r = nd2;
nnode[cnt].sum = 0;
return cnt++;
}
int build(int n) {
sz = 1;
while (sz < n)sz <<= 1;
return createTree(0, sz - 1);
}
int add(int v, int tl, int tr, int pos, int val) {
if (tl == tr) {
nnode[cnt].sum = val + nnode[v].sum;
return cnt++;
}
int tm = (tl + tr) >> 1;
if (pos <= tm) {
int nd = add(nnode[v].l, tl, tm, pos, val);
nnode[cnt].l = nd;
nnode[cnt].r = nnode[v].r;
nnode[cnt].sum = nnode[nd].sum + nnode[nnode[v].r].sum;
return cnt++;
} else {
int nd = add(nnode[v].r, tm + 1, tr, pos, val);
nnode[cnt].l = nnode[v].l;
nnode[cnt].r = nd;
nnode[cnt].sum = nnode[nd].sum + nnode[nnode[v].l].sum;
return cnt++;
}
}
int add(int root, int pos, int val) {
return add(root, 0, sz - 1, pos, val);
}
int getSum(int v, int tl, int tr, int l, int r) const {
if (tl > tr)return 0;
if (tl > r || tr < l)return 0;
if (tl >= l && tr <= r)return nnode[v].sum;
int tm = (tl + tr) >> 1;
return getSum(nnode[v].l, tl, tm, l, r) + getSum(nnode[v].r, tm + 1, tr, l, r);
}
int getSum(int root, int l, int r) const {
return getSum(root, 0, sz - 1, l, r);
}
};
int query(int x, int l, int r, const vector<int>& roots, const SegTree& tree) {
if (l == 0)return tree.getSum(roots[r], x, maxP - 1);
else return tree.getSum(roots[r], x, maxP - 1) - tree.getSum(roots[l - 1], x, maxP - 1);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++)cin >> a[i];
SegTree tree;
int root = tree.build(maxP);
vector<int> roots(n);
roots[0] = tree.add(root, a[0] - 1, 1);
for (int i = 1; i < n; i++) {
roots[i] = tree.add(roots[i - 1], a[i] - 1, 1);
}
for (int i = 0; i < q; i++) {
int l, r;
cin >> l >> r;
l--;
r--;
int left = 1;
int right = r - l + 2;
while (right - left > 1) {
int x = (right + left) >> 1;
if (query(x - 1, l, r, roots, tree) >= x) {
left = x;
} else {
right = x;
}
}
cout << left << '\n';
}
}
