뜨거운 감자

뜨거운 감자는 학교에서 아이들이 즐겨 하는 놀이다. 규칙은 단순하다. 감자를 든 아이가 다른 아이에게 감자를 던지고, 놀이를 지켜보지 않던 선생님이 어느 순간 놀이가 끝났다고 말한다. 그 순간 감자를 들고 있는 아이가 진다.

한 선생님이 급식 줄에서 하는 변형 규칙을 제안했다. 아이들은 줄에서 선 자리에 따라 1번부터 $N$번까지 번호를 받고, 1번이 줄의 맨 앞이다. 아이마다 수가 적힌 종이를 한 장씩 받고, 감자를 받으면 자기 종이에 적힌 자리의 아이에게 감자를 넘겨야 한다. 감자가 줄의 $X$번 이하 자리에 놓이면 놀이는 선생님의 승리로 끝난다. $X$는 놀이를 시작하기 전에 정하고, 1 이상 $N$ 이하다. 감자가 $X$번 이하 자리에 한 번도 놓이지 않으면 놀이는 영원히 끝나지 않고, 대신 아이들이 이긴다. 다음 날 모두 급식 할인을 받는다.

놀이는 선생님이 줄의 어느 아이에게 감자를 던지면서 시작한다. 겨냥이 정확하지 않아서 선생님은 줄의 $L$번부터 $R$번까지 가운데 한 아이에게 같은 확률로 던진다는 것만 보장할 수 있다. 선생님이 처음 던져 넣은 자리도 감자가 놓인 자리로 센다. 즉 감자를 처음 받은 아이의 번호가 $X$ 이하이면 놀이는 그 자리에서 끝난다.

선생님은 여러 구간을 후보로 놓고, 각 구간마다 놀이가 가장 공평해지는 $X$를 알고 싶다. 여기서 공평하다는 것은 놀이가 끝날 확률과 끝나지 않을 확률의 차이가 가장 작다는 뜻이다. 아이들이 받은 종이와 후보 구간이 주어질 때, 구간마다 그 $X$를 구하라. 같은 정도로 공평한 $X$가 여러 개면 줄의 앞쪽에 더 가까운 값, 즉 가장 작은 $X$를 답한다.

첫 줄에 정수 $N$과 $Q$가 주어진다. 둘째 줄에 $N$개의 정수 $p_1, p_2, \dots, p_N$이 주어지고, $p_i$는 $i$번 아이가 받은 종이에 적힌 수다. 이어지는 $Q$개의 줄에는 각각 두 정수 $L$과 $R$이 주어지고, 선생님이 후보로 놓은 구간을 뜻한다.

제한

• $2 \le N \le 50000$
• $1 \le Q \le 100000$
• $1 \le p_i \le N$
• $1 \le L \le R \le N$

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 구간에 대해 선생님이 골라야 하는 정수 $X$를 출력한다.