#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define make_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 Rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 2e5 + 200;
const int M = 1e6;
const int inf = 2e9 + 3;
const ll INF = 1e18;
int n, q;
int a[N];
vector<int> t[N * 4], L[N * 4], R[N * 4];
void build(int v = 1, int tl = 1, int tr = n) {
for (int i = tl; i <= tr; ++i) {
t[v].push_back(a[i]);
}
sort(t[v].begin(), t[v].end());
if (tl == tr) {
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm + 1, tr);
L[v].resize(sz(t[v]));
R[v].resize(sz(t[v]));
for (int i = 0; i < sz(t[v]); ++i) {
L[v][i] = lower_bound(t[2 * v].begin(), t[2 * v].end(), t[v][i]) - t[2 * v].begin();
R[v][i] = lower_bound(t[2 * v + 1].begin(), t[2 * v + 1].end(), t[v][i]) - t[2 * v + 1].begin();
}
}
int get(int l, int r, int id, int v = 1, int tl = 1, int tr = n) {
if (r < tl || tr < l || id == sz(t[v])) {
return 0;
}
if (l <= tl && tr <= r) {
return sz(t[v]) - id;
}
int tm = (tl + tr) / 2;
return get(l, r, L[v][id], v * 2, tl, tm) + get(l, r, R[v][id], v * 2 + 1, tm + 1, tr);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
build();
for (int i = 1, l, r; i <= q; ++i) {
cin >> l >> r;
int tl = 1, tr = n, ansH = 1;
while (tl <= tr) {
int tm = (tl + tr) / 2;
int h = tm;
int id = lower_bound(t[1].begin(), t[1].end(), h) - t[1].begin();
if (get(l, r, id) >= h) {
ansH = h;
tl = h + 1;
}
else {
tr = h - 1;
}
}
cout << ansH << '\n';
}
}
