#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; }