34880번 - 두 번째로 큰 수 인터랙티브

문제

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

숨겨진 길이 $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$)

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

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

출력

제한

인터랙션

당신은 표준 출력에 다음 연산을 각 줄에 출력하는 것으로, 채점 시스템과 인터랙션할 수 있다. 각 토큰은 공백으로 구분하며, 각 연산의 끝에 개행문자를 출력하여야 한다.

당신은 쿼리의 정답을 구하기 위해 채점 시스템에게 다음과 같은 연산을 전체 쿼리에서 총합하여 최대 150ドル,000円$회 할 수 있다.

• ? $i$ $j$: $A_i$와 $A_j$를 비교한다.
  • 만약 $A_i < A_j$라면 <이 다음 줄에 입력으로 주어진다.
  • 만약 $A_i > A_j$라면 >이 다음 줄에 입력으로 주어진다.

쿼리의 정답을 알아냈다면 다음과 연산을 통해 정답을 제출한다.:

• ! $x$: $A_x$가 두 번째로 큰 수임을 의미한다.
  • $l \leq x \leq r$
  • 정답 제출 연산 이후에는 다음 쿼리 $l$ $r$이 다음 줄에 공백으로 구분되어 입력으로 주어진다. (1ドル \le l < r \le N$)
  • 만약 해당 연산으로 답한 쿼리가 $Q$번째 쿼리였다면, 다음 입력은 주어지지 않으며 프로그램을 종료해야 한다.

만약 연산이 잘못된 출력이거나 제한을 초과하였다면 당신은 -1을 다음 줄에 입력받으며 이 입력이 주어질 경우 프로그램을 즉시 종료해야 한다.

채점 시스템은 적응적이지 않다. 즉 처음에 배열 $A$는 정해져 있으며 상호작용 도중에 $A$를 바꾸지 않는다.

각 연산 이후에는 표준 출력 버퍼를 비워야 한다.

각 언어별로 표준 출력 버퍼를 비우는 방법은 다음과 같다. 기타 언어의 경우, 언어의 레퍼런스 페이지를 참조하여라.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java, Kotlin: System.out.flush()
• Python: sys.stdout.flush()

노트