#include <bits/stdc++.h>
using namespace std;
const int B = 500;
struct FenwickTree {
vector<int> tree;
FenwickTree() {
tree.resize((int)2e5 + 5, 0);
}
void update(int x, int sign) {
for (; x; x -= x & -x)
tree[x] += sign;
}
int get(int x) {
int res = 0;
for (; x <= (int)2e5; x += x & -x)
res += tree[x];
return res;
}
};
int n, q;
int a[200005];
int l[200005], r[200005], id[200005], ans[200005];
FenwickTree ft;
bool comp(int u, int v) {
if (l[u] / B != l[v] / B)
return l[u] / B < l[v] / B;
return r[u] < r[v];
}
void add(int u, int sign) {
ft.update(a[u], sign);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for (int i = 1; i <= n; ++ i)
cin >> a[i];
for (int i = 1; i <= q; ++ i) {
cin >> l[i] >> r[i];
id[i] = i;
}
sort(id + 1, id + 1 + q, comp);
for (int i = 1, curL = 2, curR = 1; i <= q; ++ i) {
int u = id[i];
while (curL > l[u]) add(-- curL, 1);
while (curL < l[u]) add(curL ++, -1);
while (curR < r[u]) add(++ curR, 1);
while (curR > r[u]) add(curR --, -1);
int lo = 0, hi = n + 1;
while (hi - lo > 1) {
int mid = (hi + lo) >> 1;
if (ft.get(mid) >= mid)
lo = mid;
else
hi = mid;
}
ans[u] = lo;
}
for (int i = 1; i <= q; ++ i)
cout << ans[i] << "\n";
return 0;
}
