Median Queries

This is an interactive problem.

There is a secret permutation $$$p$$$ ($$$1$$$-indexed) of numbers from $$$1$$$ to $$$n$$$. More formally, for $$$1 \leq i \leq n$$$, $$$1 \leq p[i] \leq n$$$ and for $$$1 \leq i < j \leq n$$$, $$$p[i] \neq p[j]$$$. It is known that $$$p[1]<p[2]$$$.

In $$$1$$$ query, you give $$$3$$$ distinct integers $$$a,b,c$$$ ($$$1 \leq a,b,c \leq n$$$), and receive the median of $$$\{|p[a]-p[b]|,|p[b]-p[c]|,|p[a]-p[c]|\}$$$.

In this case, the median is the $$$2$$$-nd element ($$$1$$$-indexed) of the sequence when sorted in non-decreasing order. The median of $$$\{4,6,2\}$$$ is $$$4$$$ and the median of $$$\{0,123,33\}$$$ is $$$33$$$.

Can you find the secret permutation in not more than $$$2n+420$$$ queries?

Note: the grader is not adaptive: the permutation is fixed before any queries are made.

For each testcase, you begin the interaction by reading $$$n$$$.

To perform a query, output "? a b c" where $$$a,b,c$$$ is the $$$3$$$ indices you want to use for the query.

Numbers have to satisfy $$$1 \leq a,b,c \leq n$$$ and $$$a \neq b$$$,$$$b \neq c$$$,$$$a \neq c$$$.

For each query, you will receive a single integer $$$x$$$: the median of $$$\{|p[a]-p[b]|,|p[b]-p[c]|,|p[a]-p[c]|\}$$$.

In case your query is invalid or you asked more than $$$2n+420$$$ queries, the interactor will print "−1" and will finish interaction. You will receive Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

When you have determined the secret permutation, output "! p[1] p[2] ... p[n]". If the secret permutation is correct, the interactor will print "1". Otherwise, the interactor will print "-1" and will finish interaction. You will receive Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded verdict.

To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Hacks:

To hack, use the following format of test:

The first line should contain a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of testcases.

The first line of each testcase should contain a single integer $$$n$$$ ($$$20 \leq n \leq 100000$$$) — the length of the secret permutation.

The following line of should contain $$$n$$$ integers $$$p[1],p[2],p[3],\ldots,p[n]$$$. $$$p[1]<p[2]$$$ and $$$p$$$ must be a permutation of integers from $$$1$$$ to $$$n$$$.

You must ensure that the sum of $$$n$$$ over all testcases does not exceed $$$100000$$$.