#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
int nsqrt;
vector<int> ft(2e5 + 5, 0);
void upd(int p, int v) {
while (p < ft.size()) {
ft[p] += v;
p += p & (-p);
}
}
int qry(int p) {
int ans = 0;
while (p > 0) {
ans += ft[p];
p -= p & (-p);
}
return ans;
}
int sufqry(int l) { return qry(ft.size() - 1) - qry(l - 1); }
bool cmp(ii a, ii b) {
if (a.first / nsqrt == b.first / nsqrt) {
return a.second < b.second;
}
return a.first < b.first;
}
int main() {
int n, q;
cin >> n >> q;
nsqrt = pow(n, 0.5);
vector<int> h(n, 0);
for (int i = 0; i < n; ++i) {
cin >> h[i];
}
vector<ii> oqueries(q, ii());
for (int i = 0; i < q; ++i) {
cin >> oqueries[i].first >> oqueries[i].second;
}
vector<ii> queries;
map<ii, int> ans;
for (auto e : oqueries) {
queries.push_back({e.first - 1, e.second - 1});
}
sort(queries.begin(), queries.end(), cmp);
int l = 0, r = -1, hind = 0;
for (auto e : queries) {
for (int i = r + 1; i <= e.second; ++i) {
upd(h[i], 1);
if (sufqry(hind + 1) >= hind + 1) {
hind += 1;
}
}
for (int i = e.second + 1; i <= r; ++i) {
upd(h[i], -1);
if (sufqry(hind) < hind) {
hind -= 1;
}
}
r = e.second;
for (int i = l; i < e.first; ++i) {
upd(h[i], -1);
if (sufqry(hind) < hind) {
hind -= 1;
}
}
for (int i = e.first; i < l; ++i) {
upd(h[i], 1);
if (sufqry(hind + 1) >= hind + 1) {
hind += 1;
}
}
l = e.first;
ans[e] = hind;
}
for (auto e : oqueries) {
cout << ans[{e.first - 1, e.second - 1}] << '\n';
}
}
