#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;
struct Node {
Node* l, * r;
int sum;
Node(Node* left, Node* right, int v) {
l = left;
r = right;
sum = v;
}
Node() {
l = nullptr;
r = nullptr;
sum = 0;
}
};
struct SegTree {
int sz = 0;
Node* createTree(int l, int r) {
if (l == r) {
Node* res = new Node(nullptr, nullptr, 0);
return res;
}
int m = (l + r) >> 1;
Node* nd1 = createTree(l, m);
Node* nd2 = createTree(m + 1, r);
Node* res = new Node(nd1, nd2, 0);
return res;
}
Node* build(int n) {
sz = 1;
while (sz < n)sz <<= 1;
return createTree(0, sz - 1);
}
Node* add(Node* v, int tl, int tr, int pos, int val) {
if (tl == tr) {
Node* nd = new Node(nullptr, nullptr, val + v->sum);
return nd;
}
int tm = (tl + tr) >> 1;
if (pos <= tm) {
Node* nd = add(v->l, tl, tm, pos, val);
Node* res = new Node(nd, v->r, nd->sum + v->r->sum);
return res;
} else {
Node* nd = add(v->r, tm + 1, tr, pos, val);
Node* res = new Node(v->l, nd, v->l->sum + nd->sum);
return res;
}
}
Node* add(Node* root, int pos, int val) {
return add(root, 0, sz - 1, pos, val);
}
int getSum(Node* 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 v->sum;
int tm = (tl + tr) >> 1;
return getSum(v->l, tl, tm, l, r) + getSum(v->r, tm + 1, tr, l, r);
}
int getSum(Node* root, int l, int r) const {
return getSum(root, 0, sz - 1, l, r);
}
};
const int maxP = 200000;
int query(int x, int l, int r, const vector<Node*>& 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(0);
cout.tie(0);
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++)cin >> a[i];
SegTree tree;
Node* root = tree.build(maxP);
vector<Node*> 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';
}
}
