Batata quente

Batata quente é uma brincadeira bastante popular entre crianças na escola. A brincadeira é simples: a criança que está com a batata a joga para uma outra criança. Em algum momento, o professor, que não está olhando para o que está acontecendo, irá dizer que a brincadeira acabou. Quando isso acontece, a criança que está com a batata perde.

Uma variação da brincadeira, jogada na fila da cantina, é proposta por um professor. As crianças estão numeradas de $1$ a $N$ de acordo com sua posição na fila, onde a criança com o número $1$ é a primeira da fila. Cada uma receberá um papel com um número, e sempre que receber a batata, deverá passá-la para a criança na posição anotada em seu papel. O jogo termina com o professor vitorioso se a batata chegar em uma posição menor ou igual a $X$ na fila, com $X$ definido no inı́cio da brincadeira. Se isso nunca acontecer, o jogo nunca termina, porém as crianças saem vitoriosas: no dia seguinte todas ganham um desconto na cantina.

O professor começa o jogo jogando a batata para alguma criança na fila. Como sua mira não é muito boa, ele só consegue garantir que vai jogar a batata para alguma criança em um invervalo $L . . . R$ da fila com a mesma probabilidade. Ele está considerando vários possı́veis intervalos da fila para iniciar a brincadeira. Para isso, o professor gostaria de descobrir, para cada um desses intervalos, qual o valor de $X$ que ele deve escolher para que o jogo seja o mais justo possı́vel, ou seja, a probabilidade de o jogo terminar seja a mais próxima possı́vel da probabilidade de o jogo não terminar.

Você deve auxiliar o professor a avaliar as propostas. Dados os papéis de cada criança da fila e vários intervalos possı́veis, responda, para cada intervalo, o valor de $X$ que torne o jogo mais justo possı́vel. Se houver empate, responda o $X$ mais próximo do inı́cio da fila.

A primeira linha da entrada contém dois inteiros, $N$ e $Q$ $(2 ≤ N ≤ 50000, 1 ≤ Q ≤ 10^5 )$. A linha seguinte contém $N$ inteiros $p_1 , p_2 . . . p_N$ $(1 ≤ p_i ≤ N )$, os valores dos papéis recebidos por cada uma das crianças. Seguem então Q linhas, cada uma com dois inteiros $L$ e $R$ $(1 ≤ L ≤ R ≤ N )$, representando um intervalo considerado pelo professor.

Imprima $Q$ linhas, cada uma contendo, para cada intervalo considerado pelo professor, o número inteiro $X$ que o professor deverá escolher para que a brincadeira seja a mais justa possı́vel.