두 번째로 큰 수

이 문제는 인터랙티브 문제입니다.

숨겨진 길이 $N$의 순열 $A$가 있다. 순열 $A$에서 다음과 같은 쿼리를 $Q$회 처리하라.

• $l$ $r$: 부분 수열 $A_l, A_{l+1}, \ldots, A_r$에서 두 번째로 큰 수의 위치를 출력한다.

건모는 자신이 세상에서 알고리즘을 가장 잘한다고 생각한다. 건모는 이 문제쯤은 두 수를 최대 $150\,000$회 비교하는 것 만으로 해결 할 수 있다. 당신이 건모가 되어 문제를 해결해보자.

쿼리를 처리하기 위해, 당신은 채점 시스템에게 다음과 같은 연산을 최대 $150\,000$회 할 수 있다.

• ? $i$ $j$: $A_i$와 $A_j$의 대소를 비교한다.

첫째 줄에 $N$과 $Q$가 공백으로 구분되어 주어진다. ($2 \leq N, Q \leq 50\,000$)

둘째 줄에 첫 번째 쿼리 $l$ $r$이 공백으로 구분되어 주어진다. ($1 \le l < r \le N$)

쿼리는 온라인이다. 즉 현재 쿼리를 답하기 전까지 다음 쿼리가 주어지지 않는다.

이후 채점 시스템과의 인터랙션이 시작된다.