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