// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;
void fast_io(){
// freopen("", "r", stdin);
// freopen("", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(); cout.tie();
cout << setprecision(9);
}
#define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
const int N = 2e5 + 5;
int n, q, cur, cur_ans, block, L[N], R[N], ans[N], idx[N], a[N], freq[N];
bool mo_comp (int i, int j){
int b1 = L[i] / block;
int b2 = L[j] / block;
if (b1 != b2) return(b1 < b2);
return (R[i] < R[j]);
}
void add(int i){
if (a[i] >= cur_ans) cur++;
freq[a[i]]++;
while (cur - freq[cur_ans] > cur_ans){
cur -= freq[cur_ans];
cur_ans++;
}
}
void remove(int i){
if (a[i] >= cur_ans) cur--;
freq[a[i]]--;
while (cur < cur_ans){
cur_ans--;
cur += freq[cur_ans];
}
}
void solve() {
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];
idx[i] = i;
}
block = sqrt(n) + 1;
sort(idx + 1, idx + q + 1, mo_comp);
int Le = 1, Ri = 0;
for (int i = 1; i <= q; i++){
int nidx = idx[i];
int l = L[nidx], r = R[nidx];
// cout << l << ' ' << r << endl;
while (Le > l) add(--Le);
while (Le < l) remove(Le++);
while (Ri < r) add(++Ri);
while (Ri > r) remove(Ri--);
ans[nidx] = cur_ans;
}
// cout << Le << ' ' << Ri << endl;
for (int i = 1; i <= q; i++) cout << ans[i] << endl;
return;
}
signed main() {
fast_io();
srand(chrono::steady_clock::now().time_since_epoch().count());
int tc = 1;
// cin >> tc;
while (tc--) solve();
return 0;
}
