#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200000 + 5;
const int MAX_NODES = MAX_N * 25;
struct PersistentSegmentTree {
int sum[MAX_NODES];
int leftChild[MAX_NODES];
int rightChild[MAX_NODES];
int nodeCount = 0;
vector<int> roots;
int limiteValor;
int createNode(int valor, int left, int right) {
++nodeCount;
sum[nodeCount] = valor;
leftChild[nodeCount] = left;
rightChild[nodeCount] = right;
return nodeCount;
}
void inicializar(int maxValor) {
limiteValor = maxValor;
roots.clear();
roots.push_back(0);
nodeCount = 0;
}
int updateNode(int node, int l, int r, int pos, int delta) {
if (pos < l || pos > r) {
return node;
}
if (l == r) {
int novoValor = sum[node] + delta;
return createNode(novoValor, 0, 0);
}
int mid = (l + r) / 2;
int left = updateNode(leftChild[node], l, mid, pos, delta);
int right = updateNode(rightChild[node], mid + 1, r, pos, delta);
int novoValor = sum[left] + sum[right];
return createNode(novoValor, left, right);
}
void atualizarVersao(int pos, int delta) {
int raizAnterior = roots.back();
int novaRaiz = updateNode(raizAnterior, 1, limiteValor, pos, delta);
roots.push_back(novaRaiz);
}
int queryNode(int node, int l, int r, int ql, int qr) {
if (!node || qr < l || r < ql) {
return 0;
}
if (ql <= l && r <= qr) {
return sum[node];
}
int mid = (l + r) / 2;
int leftSum = queryNode(leftChild[node], l, mid, ql, qr);
int rightSum = queryNode(rightChild[node], mid + 1, r, ql, qr);
return leftSum + rightSum;
}
int query(int versaoIndex, int l, int r) {
if (l > r) return 0;
return queryNode(roots[versaoIndex], 1, limiteValor, l, r);
}
} arvore;
int main() {
int qntElementos, qntConsultas;
cin >> qntElementos >> qntConsultas;
arvore.inicializar(qntElementos);
for (int i = 1; i <= qntElementos; i++) {
int valor;
cin >> valor;
arvore.atualizarVersao(valor, 1);
}
while (qntConsultas--) {
int esquerda, direita;
cin >> esquerda >> direita;
int resposta = 0;
int l = 1, r = qntElementos;
while (l <= r) {
int meio = (l + r) / 2;
int qtdNoPrefixoDireita = arvore.query(direita, meio, qntElementos);
int qtdNoPrefixoEsquerda = arvore.query(esquerda - 1, meio, qntElementos);
int quantidade = qtdNoPrefixoDireita - qtdNoPrefixoEsquerda;
if (quantidade >= meio) {
resposta = meio;
l = meio + 1;
} else {
r = meio - 1;
}
}
cout << resposta << '\n';
}
return 0;
}
