#include "bits/stdc++.h"
using namespace std;
#define F first
#define S second
#define sz(x) int((x).size())
using ll = long long;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
assert(l <= r);
return uniform_int_distribution<ll> (l, r)(rng);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
const int N = 2e5 + 3;
struct Query{
int l, r, id;
} d[N];
struct Fenwick{
#define gb(x) (x) & -(x)
vector<ll> bit;
int n;
void init(int _n){
bit.resize(_n + 4, 0);
n = _n;
}
void upd(int x, ll val){
while(x <= n){
bit[x] += val;
x += gb(x);
}
}
ll get(int x){
ll res = 0;
while(x > 0){
res += bit[x];
x -= gb(x);
}
return res;
}
} fen;
int n, q, p[N], ans, res[N];
void add(int x){
fen.upd(p[x], 1);
if(fen.get(N) - fen.get(ans) >= ans + 1)
++ans;
}
void del(int x){
fen.upd(p[x], -1);
if(fen.get(N) - fen.get(ans - 1) < ans)
--ans;
}
void solve(){
fen.init(N);
cin >> n >> q;
for(int i = 1; i <= n; ++i)
cin >> p[i];
for(int i = 1; i <= q; ++i){
cin >> d[i].l >> d[i].r;
d[i].id = i;
}
int S = sqrt(n);
sort(d + 1, d + q + 1, [S](const Query &A, const Query &B){
return A.l / S != B.l / S ? A.l / S < B.l / S : A.r < B.r;
});
int l = 1, r = 0;
for(int i = 1; i <= q; ++i){
while(r < d[i].r) add(++r);
while(r > d[i].r) del(r--);
while(l < d[i].l) del(l++);
while(l > d[i].l) add(--l);
res[d[i].id] = ans;
}
for(int i = 1; i <= q; ++i)
cout << res[i] << '\n';
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(0);
int test = 1;
// cin >> test;
for(int i = 1; i <= test; ++i){
// cout << "Case #" << i << ": ";
solve();
}
cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
return 0;
}
