#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
struct Vertex {
Vertex *l, *r;
int cnt;
Vertex(int val) : l(nullptr), r(nullptr), cnt(val) {}
Vertex(Vertex* l, Vertex* r) : l(l), r(r), cnt(0) {
if (l) cnt += l->cnt;
if (r) cnt += r->cnt;
}
};
struct persistenSegmentTree {
Vertex* build(int l, int r) {
if (l == r) return new Vertex(0);
int mid = (l+r)>>1;
return new Vertex(build(l, mid), build(mid+1, r));
}
Vertex* update(Vertex* v, int l, int r, const int val) {
if (l == r) return new Vertex(v->cnt+1);
int mid = (l+r)>>1;
if (val <= mid) return new Vertex(update(v->l, l, mid, val), v->r);
return new Vertex(v->l, update(v->r, mid+1, r, val));
}
int query(Vertex* v1, Vertex* v2, int l, int r, const int k) {
if (l == r) return (k <= l? v2->cnt - v1->cnt:0);
int mid = (l+r)>>1;
if (k <= mid) return (v2->r->cnt - v1->r->cnt) + query(v1->l, v2->l, l, mid, k);
return query(v1->r, v2->r, mid+1, r, k);
}
};
int main(int argc, const char* argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector <int> arr(n+1);
for(int i = 1; i <= n; ++i) {
cin >> arr[i];
}
persistenSegmentTree tree;
vector <Vertex*> version(n+1);
version[0] = tree.build(1, MAXN);
for(int i = 1; i <= n; ++i) {
version[i] = tree.update(version[i-1], 1, MAXN, arr[i]);
}
while (q--) {
int left, right;
cin >> left >> right;
int l = 1, r = MAXN;
int best = 0;
while (l <= r) {
int mid = (l+r)>>1;
int cnt = tree.query(version[left-1], version[right], 1, MAXN, mid);
if (cnt >= mid) {
best = mid;
l = mid+1;
}
else r = mid-1;
}
cout << best << '\n';
}
arr.clear();
return 0;
}
