#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
// Structure to store query information
struct Query {
int l, r, idx, block;
};
// Comparison function for sorting queries
bool compareQueries(const Query& a, const Query& b) {
if (a.block != b.block) return a.block < b.block;
return a.r < b.r;
}
class Solution {
private:
int n, q;
vector<int> citations;
vector<int> answers;
vector<int> count;
// Calculate h-index for current range
int calculateHIndex() {
int total = 0;
for (int h = n; h >= 0; h--) {
total += count[h];
if (total >= h) {
return h;
}
}
return 0;
}
public:
void solve() {
// Input
cin >> n >> q;
// Read citations
citations.resize(n);
for (int i = 0; i < n; i++) {
cin >> citations[i];
}
// Prepare queries
vector<Query> queries(q);
int blockSize = sqrt(n);
for (int i = 0; i < q; i++) {
cin >> queries[i].l >> queries[i].r;
queries[i].l--; // Convert to 0-based indexing
queries[i].r--;
queries[i].idx = i;
queries[i].block = queries[i].l / blockSize;
}
// Sort queries
sort(queries.begin(), queries.end(), compareQueries);
// Prepare data structures
answers.resize(q);
count.resize(n + 1, 0);
// Initial state
int currentL = 0, currentR = -1;
// Process queries using MO's algorithm
for (const Query& query : queries) {
// Extend/shrink range to match query
while (currentR < query.r) {
currentR++;
if (citations[currentR] >= n) {
count[n]++;
} else {
count[citations[currentR]]++;
}
}
while (currentR > query.r) {
if (citations[currentR] >= n) {
count[n]--;
} else {
count[citations[currentR]]--;
}
currentR--;
}
while (currentL > query.l) {
currentL--;
if (citations[currentL] >= n) {
count[n]++;
} else {
count[citations[currentL]]++;
}
}
while (currentL < query.l) {
if (citations[currentL] >= n) {
count[n]--;
} else {
count[citations[currentL]]--;
}
currentL++;
}
// Calculate h-index for current range
int hIndex = 0;
int total = 0;
for (int h = n; h >= 0; h--) {
total += count[h];
if (total >= h) {
hIndex = h;
break;
}
}
answers[query.idx] = hIndex;
}
// Output answers in original query order
for (int ans : answers) {
cout << ans << "\n";
}
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Solution solution;
solution.solve();
return 0;
}
