Double up

AGCU 섬에는 $N$개의 구역이 존재하고, 이 중 한 구역에는 보물이 숨겨져 있다.

nflight11과 jthis는 각자 탐지기를 들고 특정 구역으로 이동할 수 있고, 원하는 순간 두 탐지기를 동시에 작동할 수 있다. 탐지기가 두 구역에 걸쳐 있거나 두 개의 탐지기가 같은 구역에 있을 경우 에러가 발생하므로 무조건 하나의 탐지기는 정확히 한 구역에 속해 있어야 한다. 두 사람은 적절한 위치에서 탐지기를 작동해 보물을 찾으려고 한다. 탐지기는 최대 $\lceil \frac{N}{2} \rceil$ 번 작동할 수 있다.

첫 번째 줄에 구역의 개수를 나타내는 정수 $N$이 주어진다. ($3 \leq N \leq 1000$)

인터랙션

다음과 같은 방법으로 탐지기를 최대 $\lceil \frac{N}{2} \rceil$ 번 작동할 수 있다. 이보다 더 많이 작동한 경우 오답을 받게 된다.

• ? $a$ $b$: nflight11이 $a$로, jthis가 $b$로 이동한 후 탐지기를 작동한다. ($1 \leq a, b \leq N; a \neq b$)
• 작동한 결과로 두 구역 중 하나에 보물이 숨겨져 있으면 $1$, 그렇지 않으면 $0$이 표준 입력으로 주어진다.
• 탐지기를 작동한 뒤 표준 출력 버퍼를 비워야 한다.

보물이 숨겨져 있는 위치를 알았다면 사용자는 다음과 같이 출력해야 한다.

• ! $x$: 보물이 숨겨져 있는 구역이 $x$임을 의미한다.

숨겨져 있는 구역을 출력한 뒤 표준 출력 버퍼를 비우고 프로그램을 즉시 종료해야 한다.

잘못된 형식으로 출력한 경우, 출력 후 버퍼를 비우지 않을 경우, 보물을 발견한 후 프로그램을 종료하지 않을 경우 예상치 못한 결과를 받을 수 있다.

다음과 같은 방법으로 출력 버퍼를 비울 수 있다.

• C --- fflush(stdout)
• C++ --- std::cout.flush()
• Python --- sys.stdout.flush()
• Java --- System.out.flush()
• 그 외의 언어는 각 언어의 Documentation을 참고한다.

*$\lceil x \rceil$: $x$보다 작지 않은 가장 작은 정수를 의미한다.