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.</p>

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. A linha seguinte contém N inteiros p₁, p₂, ⋯, p_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, representando um intervalo considerado pelo professor.</p>

Restrições

• 2 ≤ N ≤ 50000
• 1 ≤ Q ≤ 10⁵
• 1 ≤ p_i ≤ N
• 1 ≤ L ≤ R ≤ N

출력 형식

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.

예제 입력 1

9 4
2 3 4 5 6 7 4 9 5
1 3
3 5
2 8
7 9

예제 출력 1

1
3
3
1

예제 입력 2

3 3
1 3 3
1 1
1 2
2 3

예제 출력 2

1
1
2