Problem Description

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.

bool compare(int a, int b)
{
    cout << "? " << a << ' ' << b << endl;
    bool t;
    cin >> t;
    return t;
}

Please fill in this function in your code. Modify it at your own risk.

Input Format

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}$.

Output Format

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.

3

1

0

0

? 1 2

? 1 3

? 2 3

! 3 1 2

Hint

The testdata satisfies $1 \le N \le 1000$.

Translated by ChatGPT 5