#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 2e5 + 5;
const ll SQ = 500;
vector<pair<pair<int,int>,int>> query;
vector<int> A;
int ans[MAXN], suff[MAXN], res = 1, cnt = 1;
void insert(int x) {
suff[A[x]]++;
if (A[x] >= res)
cnt++;
if (cnt - suff[res] > res) {
cnt -= suff[res];
res++;
}
}
void omit(int x) {
suff[A[x]]--;
if (A[x] >= res)
cnt--;
if (cnt < res) {
res--;
cnt += suff[res];
}
}
int main() {
fast
int N, Q;
cin >> N >> Q;
A = vector<int>(N+1);
query = vector<pair<pair<int,int>,int>>(Q);
for (int i = 1; i <= N; i++)
cin >> A[i];
for (int i = 0; i < Q; i++) {
cin >> query[i].f.f >> query[i].f.s;
query[i].s = i;
}
sort(query.begin(), query.end(), [&](pair<pair<int,int>,int> a, pair<pair<int,int>,int> b) {
return make_pair(a.f.f / SQ, a.f.s) < make_pair(b.f.f / SQ, b.f.s);
});
int l = 1, r = 1;
suff[A[1]]++;
for (auto u : query) {
int new_l = u.f.f;
int new_r = u.f.s;
while (new_l < l) {
l--;
insert(l);
}
while (new_r > r) {
r++;
insert(r);
}
while (new_l > l) {
omit(l);
l++;
}
while (new_r < r) {
omit(r);
r--;
}
ans[u.s] = res;
}
for (int i = 0; i < Q; i++)
cout << ans[i] << "\n";
}
