#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int TAM_BLOCO = 450;
int citacoes[MAXN];
int frequencia[MAXN];
int respostas[MAXN];
int esquerda[MAXN];
int direita[MAXN];
int ordem[MAXN];
int inicio = 1;
int fim = 0;
int hAtual = 0;
int quantidadeMaiorIgual = 0;
void adicionar(int posicao) {
int valor = citacoes[posicao];
if (valor >= MAXN) {
valor = MAXN - 1;
}
frequencia[valor]++;
if (valor >= hAtual) {
quantidadeMaiorIgual++;
}
if (quantidadeMaiorIgual - frequencia[hAtual] >= hAtual + 1) {
quantidadeMaiorIgual -= frequencia[hAtual];
hAtual++;
}
}
void remover(int posicao) {
int valor = citacoes[posicao];
if (valor >= MAXN) {
valor = MAXN - 1;
}
frequencia[valor]--;
if (valor >= hAtual) {
quantidadeMaiorIgual--;
}
if (quantidadeMaiorIgual < hAtual) {
hAtual--;
quantidadeMaiorIgual += frequencia[hAtual];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> citacoes[i];
if (citacoes[i] > n) {
citacoes[i] = n + 1;
}
}
for (int i = 0; i < q; i++) {
cin >> esquerda[i] >> direita[i];
ordem[i] = i;
}
sort(ordem, ordem + q, [&](int a, int b) {
int blocoA = esquerda[a] / TAM_BLOCO;
int blocoB = esquerda[b] / TAM_BLOCO;
if (blocoA != blocoB) {
return blocoA < blocoB;
}
if (blocoA % 2 == 0) {
return direita[a] < direita[b];
} else {
return direita[a] > direita[b];
}
});
for (int i = 0; i < q; i++) {
int id = ordem[i];
while (fim < direita[id]) {
adicionar(++fim);
}
while (inicio > esquerda[id]) {
adicionar(--inicio);
}
while (fim > direita[id]) {
remover(fim--);
}
while (inicio < esquerda[id]) {
remover(inicio++);
}
respostas[id] = hAtual;
}
for (int i = 0; i < q; i++) {
cout << respostas[i] << "\n";
}
return 0;
}
