D. The Hard One
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This problem has different versions. The differences between them are in the permutation restriction, the limit of queries and the setprecision line in the interactor code.

This is an interactive problem.

There is a hidden permutation$$$^{\text{∗}}$$$ of length $$$n$$$ ($$$2 \leq n \leq 100$$$), $$$a_1, a_2, ..., a_n$$$, with the added restriction that $$$\mathbf{a_1 \lt a_2}$$$. Your goal is to determine this permutation.

You can perform the following query multiple times:

  • Send $$$n$$$ numbers, $$$b_1, b_2, ..., b_n$$$.
  • The numbers are summed in the order $$$b_{a_1}, b_{a_2}, ..., b_{a_n}$$$.
  • You receive the result of this sum.

You can perform at most $$$\mathbf{2n}$$$ queries.

Confused?

Here is the C++ code of the interactor that performs the sum:

void sum_numbers(std::vector<float> numbers) {

  float sum = 0;
  for (auto idx : hidden_permutation) {
    sum += numbers[idx - 1];
  }

  std::cout << std::setprecision(std::numeric_limits<float>::max_digits10);

  std::cout << sum << std::endl;
}

Assume that before this function is called, numbers was computed by reading each number in your query as a double and then casting it to a float (not shown to keep this free of testlib code).

At the moment of release of the contest, the interactor was compiled with the default codeforces compiler gcc14-64-msys2-g++23 and the only libraries used were testlib.h and bits/stdc++.h. There are no pragmas or any unusual operation, but if you want to read the full interactor code, it's available here: https://pastebin.com/xae0vHzt

Good luck.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array that contains every integer from $$$1$$$ to $$$n$$$ exactly once, in any order.

Input

The first line contains an integer $$$n$$$, the size of the hidden permutation.

Interaction

To make a query, you must output a line starting with a ?, followed by $$$n$$$ space separated numbers.

? b_1 b_2 ... b_n

After printing each query, do not forget to output the end of line and flush the output$$$^{\text{∗}}$$$. Otherwise, you will get Idleness limit exceeded verdict.

Then you must read a number corresponding to the result of the sum.

To guess the hidden permutation, you must output a line starting with a !, followed by $$$n$$$ space separated integers.

! a_1 a_2 ... a_n

$$$^{\text{∗}}$$$ To flush, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
4

10
Output

? 1 2 3 4

! 1 4 2 3