문제

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

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

• : 부분 수열 에서 두 번째로 큰 수의 위치를 출력한다.

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

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

• ? : 와 의 대소를 비교한다.

입력

첫째 줄에 과 가 공백으로 구분되어 주어진다. ()

둘째 줄에 첫 번째 쿼리 이 공백으로 구분되어 주어진다. ()

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

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

인터랙션

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

당신은 쿼리의 정답을 구하기 위해 채점 시스템에게 다음과 같은 연산을 언제든지 최대 회 할 수 있다.

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

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

• ! : 가 두 번째로 큰 수임을 의미한다.

*  $l \leq x \leq r$

*  정답 제출 연산 이후에는 다음 쿼리 $l$ $r$이 다음 줄에 공백으로 구분되어 입력으로 주어진다. 만약 해당 연산으로 답한 쿼리가 $Q$번째 쿼리였다면, 프로그램을 종료해야 한다.

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

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

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

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

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