22958번 - 안산 탐지기 인터랙티브

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

국렬이는 주말에 연세대 근처에 있는 안산 공원에 갈 것이다. 안산 공원에서 산책을 한 뒤에 산 위로 올라갈 것이다.

산은 $N$개의 봉우리가 균등한 간격으로 일렬로 서있으며, $i$번째 봉우리의 높이는 $h_i$ ($1 \le h_i \le 1\,000\,000\,000$) 로 각 봉우리의 높이는 모두 다르다. 국렬이는 운동하기 위해서 가장 높은 봉우리로 갈 것이다. 그러나 국렬이는 각 봉우리의 높이가 어느 정도인지 모르기 때문에 봉우리의 높이를 측정하기 위해서 집에서 탐지기 $N$개와 배터리 $2N-1$개를 가져왔다.

탐지기를 사용하기 위해서는 우선 첫 번째로 탐지하는 봉우리를 지정한다. 그리고 $i$번째 탐지기로 배터리 $j$개를 사용하면 지정한 봉우리부터 시작해서 $i$칸 간격으로 연속된 봉우리 $j$개를 확인할 수 있다. 예를 들어서 첫 번째로 탐지할 봉우리로 2번째 봉우리를 지정한 후에 3번째 탐지기로 배터리를 3개를 사용하면 그림과 같이 2번째, 5번째, 8번째 봉우리를 탐지할 수 있다. 이렇게 해서 탐지한 산들 중 최대 높이가 탐지기의 결과 값으로 나온다.

탐지기는 1회용으로 재사용이 불가능하다. 그리고 탐지기가 매우 비싸기 때문에 탐지기 사용 횟수를 최대 20번으로 제한할 것이다. 가장 높은 봉우리의 위치를 구해보자.

입력의 첫 번째 줄에 산을 이루고 있는 봉우리의 수인 $N$이 주어진다. ($1 \le N \le 500\,000$)

다음을 표준 출력 스트림(stdout)으로 한 줄에 출력하여 탐지기를 사용할 수 있으며, 이에 대한 답으로 탐지한 봉우리의 최대 높이가 입력으로 주어진다.

• ? s a b : 첫 번째로 탐지할 봉우리로 $s$번째 봉우리를 지정한 후, $a$번째 탐지기로 배터리 $b$개를 사용한다. ($1 \le s, a, b \le N$)

각 질문을 출력한 후에는 반드시 표준 출력 버퍼를 flush해 주어야 하고, 표준 입력 스트림(stdin)을 통해 질문에 대한 답을 입력받아야 한다. 질문에 대한 답을 입력받지 않으면 런타임 에러를 받게 된다. 탐지기의 최대 사용 횟수는 20번, 배터리의 최대 사용 개수는 $2N-1$개로 그 이상으로 사용하게 된 경우 틀렸습니다!를 받는다. 탐지하는 범위가 $N$번째 봉우리를 넘어가는 경우와 같은 탐지기를 2번 이상 사용한 경우도 틀렸습니다!를 받는다.

만약 가장 높은 봉우리의 위치를 알아낸 경우, 표준 출력 스트림으로 다음을 한 줄에 출력한다.

• ! x : $x$번째 봉우리가 가장 높은 봉우리다.

그 후 반드시 표준 출력 버퍼를 flush해야 하고, 프로그램을 종료한다. 이것은 질문 횟수에 포함되지 않는다.

언어별로 표준 출력 버퍼를 flush하는 방법은 다음과 같다.

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