#include <bits/stdc++.h>
using namespace std;
#define int long long
int sqrtN;
bool comp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
if (a.first.first / sqrtN == b.first.first / sqrtN)
return a.first.second < b.first.second;
return a.first.first / sqrtN < b.first.first / sqrtN;
}
vector<int> tree;
void upd(int n, int x) {
while (n < tree.size()) {
tree[n] += x;
n += n & (-n);
}
}
int qry(int a) {
int ans = 0;
while (a != 0) {
ans += tree[a];
a -= a & (-a);
}
return ans;
}
int rqry(int a) {
if (a <= 0) return 0;
return qry(tree.size() - 1) - qry(a - 1);
}
signed main() {
int n, q, p, a, b;
cin >> n >> q;
sqrtN = pow(n, 0.5f);
int numB = (n + sqrtN - 1) / sqrtN;
vector<int> P;
vector<pair<pair<int, int>, int>> queries;
for (int i = 0; i < n; i++) {
cin >> p;
P.push_back(p);
}
for (int i = 0; i < q; i++) {
cin >> a >> b;
a--, b--;
queries.push_back({ { a, b }, i });
}
sort(queries.begin(), queries.end(), comp);
tree = vector<int>(200005, 0);
int ans = 0;
vector<int> anss(q, 0);
pair<int, int> prevquery = { 0, 0 };
for (int i = 0; i < q; i++) {
auto query = queries[i];
int s = query.first.first;
int e = query.first.second + 1;
while (prevquery.first < s) {
upd(P[prevquery.first], -1);
if (rqry(ans) < ans)
ans--;
prevquery.first++;
}
while (prevquery.first > s) {
upd(P[prevquery.first - 1], 1);
if (rqry(ans + 1) >= ans + 1)
ans++;
prevquery.first--;
}
while (prevquery.second < e) {
upd(P[prevquery.second], 1);
if (rqry(ans + 1) >= ans + 1)
ans++;
prevquery.second++;
}
while (prevquery.second > e) {
upd(P[prevquery.second - 1], -1);
if (rqry(ans) < ans)
ans--;
prevquery.second--;
}
anss[query.second] = ans;
}
for (int i : anss)
cout << i << '\n';
}
