P10451 Innovative Business

There are $N$ elements, numbered $1,2,\dots,N$. For every pair of elements, their order relation is determined. The relation is antisymmetric, but it is not transitive. **Note**: There are no two elements that are equal. In other words, the order relation can be seen as an arbitrary directed graph consisting of $N$ vertices and $\frac{N \times (N-1)}{2}$ directed edges. However, this is an interactive problem. You cannot know these relations all at once. You must obtain information by asking no more than $10000$ questions, and each question can only reveal the relation between two elements. Now you need to arrange these $N$ elements in a line so that every element is smaller than the element adjacent to it on the right. You can use our preset bool function `compare` to get the order relation between two elements. For example, for two elements numbered $a$ and $b$, if element $a$ is smaller than element $b$, then `compare(a,b)` returns true; otherwise it returns false. After sorting the $N$ elements, output their numbers as an array. If the answer is not unique, you may output any one. --- To fit the OJ, the interactive format of this problem has been modified into I/O interaction. ```cpp bool compare(int a, int b) { cout

The interactive library first provides a positive integer $N$, which is the number of elements. After that, for each answer, the interactive library returns $1$ or $0$ to indicate the order relation. $1$ means $\text{true}$, and $0$ means $\text{false}$.

You can ask questions using the `compare` function in the statement. If you want to write the query by yourself, the query format is `? a b`. Before outputting the answer, please output an exclamation mark `!` first. Then output these $n$ numbers separated by spaces. See Sample #1 for details.

The testdata satisfies $1 \le N \le 1000$. Translated by ChatGPT 5