# COI 24 Koreografija

https://www.acmicpc.net/problem/31982

There are a line of $1000$ dancers, each wearing an integer from $1$ to $1000$ such that each dancer does not have the same integer.

Tvrtko watched the dancers, and he observes each interval of dancers. To decide if he likes an interval of dancers $[a,b]$, he counts the number of pairs of dancers $x,y$ such that $a \leq x < y \leq b$, such that the number written on dancer $x$ is larger than that of $y$. If and only if the number of such pairs is odd, he likes the interval.

You are curious about the order of dancers. To determine this, you can ask Tvrtko whether he liked the interval $[a,b]$. Determine the order of the dancers in as few queries as possible.

## Interaction

This is an interactive task.

Your program can send queries by writing to standard output. Each query should be printed on a separate line in the format "? $a$ $b$", where $a$ and $b$ are natural numbers such that $1 ≤ a ≤ b ≤ 1000$. The numbers $a$ and $b$ represent the positions of dancers that define the observed interval.

After printing each query, your program should flush the output and read the response to the query from standard input – a number from the set ${0, 1}$ representing Tvrtko's opinion on the interval. The number $1$ indicates that Tvrtko liked that interval, and $0$ indicates that he did not.

Your program can send up to $500,000$ such queries.

Once your program has reconstructed the numbers on the dancers' costumes, it should print a single line to standard output containing the symbol "!". After this, **flush** the output, and then output the sequence of dancers, and then **flush** the output once more.

## Scoring

Let $Q$ be the maximum number of queries your program sends across all test cases.

If $Q > 500,000$
- your program will score $0$ points.

If $40,000 \leq Q \leq 500,000$
- Your sure is $30 + 70 \cdot \frac{1/Q - 1/500,000}{1/40,000 - 1/500,000}$

If $Q \leq 40,000$
- Your score is $100$

## Example

Although the number of dancers in the problem will always be $1000$, here is an example interaction as if there were only $4$ dancers.

Suppose the numbers of the dancers were `2 1 4 3`.
| Output | Input | Note |
|--------|-------|------------------------------------|
| ? 1 2 | 1 | Tvrtko counted one pair. |
| ? 1 3 | 1 | Tvrtko counted one pair. |
| ? 1 4 | 0 | Tvrtko counted two pairs. |
| ? 2 3 | 0 | Tvrtko counted zero pairs. |
| ? 2 4 | 1 | Tvrtko counted one pair. |
| ? 3 4 | 1 | Tvrtko counted one pair. |
| ! | | Numbers are discovered, printed in order. |
| 2 1 4 3 | | |