Description

“The Big Prize” is a well-known TV game show. This time you are lucky to reach the final round. There are $n$ boxes in a row from left to right, numbered from $0$ to $n-1$, and you are standing in front of them. Each box contains exactly one prize, and you must open a box to see which prize it holds. There are $v\leq5$ distinct types of prizes. These $v$ types are ordered from $1$ to $v$ in decreasing order of value.

The type $1$ prize is a diamond, the most valuable. Across all boxes there is exactly one diamond. The type $v$ prize is a lollipop, the least valuable. To make the game more exciting, cheaper prizes are far more numerous than expensive prizes. More specifically, for every $t$ with $2\leq t \leq v$, if there are $k$ prizes of type $t-1$, then there are strictly more than $k^2$ prizes of type $t$.

Your goal is to win the diamond. At the end of the game, you must open one box and take the prize inside. Before choosing which box to open, you may ask the host, Rambod, some questions. In each question, you choose a box index $i$. Rambod answers with an array $a$ of two integers. They mean:

• Among the boxes to the left of box $i$, there are exactly $a[0]$ boxes whose prizes are more valuable than the prize in box $i$.
• Among the boxes to the right of box $i$, there are exactly $a[1]$ boxes whose prizes are more valuable than the prize in box $i$.

For example, suppose $n=8$, and in your query you choose $i=2$. Rambod’s answer is $a=[1,2]$. This means:

• Among boxes $0$ and $1$, exactly one box has a prize more valuable than the prize in box $2$.
• Among boxes $3,4,\cdots,7$, exactly $2$ boxes have prizes more valuable than the prize in box $2$.

Your task is to find the box containing the diamond by asking as few questions as possible.

Input Format

When your program starts, it should read a positive integer $n$.

You may issue queries in the following format:

• ? i
  Meaning you choose to ask about box $i$. You must ensure $0\leq i<n$.
  Then you should read two integers a[0] a[1], which is the interactor’s response.

You may report your answer in the following format:

• ! i
  Meaning you are certain that the diamond is in box $i$.
  Then you must terminate your program immediately.

Output Format

After issuing a query, do not forget to flush the output buffer. You may use:

• fflush(stdout) or cout.flush() in C++.
• stdout.flush() in Python.
• For other languages, refer to their documentation.

8

0 3

0 1

1 2

0 0

2 1

2 1

1 0

3 0

? 0

? 1

? 2

? 3

? 4

? 5

? 6

? 7

! 3

Hint

Sample explanation

8
3 2 3 1 3 3 2 3

The figure illustrates this example. The upper part shows the prize type in each box. The lower part illustrates the query ? 2.

Constraints

• $3\leq n \leq200000$.
• The prize type in each box is between $1$ and $v$ (inclusive).
• There is exactly one type $1$ prize.
• For all $2\leq t \leq v$, if there are $k$ prizes of type $t-1$, then there are strictly more than $k^2$ prizes of type $t$.

Subtasks and Scoring

1. (20 points) There is exactly $1$ diamond and $n-1$ lollipops (so $v=2$). You may ask at most $10000$ queries.
2. (80 points) No additional constraints.

In subtask 2 you can receive partial credit. Let $q$ be the maximum number of queries you use over all testdata in this subtask; then your score for this subtask is computed as follows:

Translated by ChatGPT 5