Background

Source: https://hsin.hr/hio2024/. The translation comes from Wenxin Yiyan. If you have a better translation, please share it in the discussion area.

Problem Description

Jura: Tvrtko, how was yesterday’s performance?
Tvrtko: It was excellent. The best part was the choreography when $1000$ dancers lined up from left to right and started performing. Each of them had a number between $1$ and $1000$ written on their costume, and all these numbers were different. But I have to say, when I saw them standing in a line, I did not like their order.
Jura: What do you mean?
Tvrtko: I looked at some consecutive intervals of dancers in the line and counted how many pairs of dancers are such that the dancer in the lower position has a higher number than the dancer in the higher position. I like it when the number of such pairs is odd.
Jura: Oh, Tvrtko, you need to see the big picture. I will handle it. But tell me, what was the order of their numbers?
Tvrtko: Well… I forgot. But I can tell you, for every consecutive interval of dancers, whether I like it or not.
Jura: So be it. We have no choice but to try to determine their numbers from that.

Input Format

This is an interactive task. Your program must communicate with the program provided by the organizers, responding to the questions asked.

Your program can send queries by writing to standard output. Each query should be printed on a separate line, and should be in the form ? a b, where $a$ and $b$ are positive integers satisfying $1 \leq a \leq b \leq 1000$. The numbers $a$ and $b$ represent the dancers’ positions of the observed interval.

After outputting each query, your program should flush the output and read from standard input the response to the query—one number from the set $\{0,1\}$, indicating Tvrtko’s opinion of that interval: $1$ means Tvrtko likes that interval, and $0$ means he does not. Your program may send at most $500000$ such queries.

Once your program has determined the numbers on the dancers’ costumes, it should print on standard output on a separate line the symbol ! followed by the required sequence of numbers from left to right. Then, your program should flush the output again and terminate.

Hint

[Explanation]

Although the number of dancers in the task is always $1000$, for illustration purposes we provide an interactive example when the number of dancers is $4$.

Assume the numbers on the dancers’ costumes, in order, are $2,1,4,3$. Below is one possible query plan:

• Query ? 1 2, Tvrtko counted one pair.
• Query ? 1 3, Tvrtko counted one pair.
• Query ? 1 4, Tvrtko counted two pairs.
• Query ? 2 3, Tvrtko counted no pairs.
• Query ? 2 4, Tvrtko counted one pair.
• Query ? 3 4, Tvrtko counted one pair.
• Output the answer using ! 2 1 4 3.

[Scoring]

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

If $Q > 5\times 10^5$, your program will score $0$ points.

Otherwise, your program’s score is based on the following table:

Translated by ChatGPT 5