Number of Distinct Numbers#12448

Number of Distinct Numbers

1 second

512 megabytes

Very hard

This is an interactive problem.

An array of integers $a$ of length $n$ is hidden from you.

You need to determine how many distinct numbers are contained in the array $a$ , using no more than $\frac{n}{2} + 1$ \frac{n}{2} + 1 queries.

You can make queries of the following form:

? $j_{1}$ j_1 $j_{2}$ j_2 $\dots$ $j_{n}$ j_n, where $j_{1}, j_{2}, \dots, j_{n}$ j_1, j_2, \ldots, j_n is a permutation of the numbers from $1$ to $n$ .

After such a query, an array $p$ of length $n$ is created by the rule: $p_{i} = a_{j_{i}}$ p_i = a_{j_i}.

In response to the query, you are given an array $b$ of length $n$ .

For each $i$ , the value $b_{i}$ b_i is equal to the number of neighbors of element $p_{i}$ p_i that are equal to it.

The value $b_{i}$ b_i can be described as: $b_{i} = c_{i 1} + c_{i 2}$ b_i = c_{i1} + c_{i2}

where $c_{i 1} = 1$ c_{i1} = 1 if $i > 1$ i > 1 and $p_{i} = p_{i - 1}$ p_i = p_{i - 1}, otherwise $c_{i 1} = 0$ c_{i1} = 0.

Similarly, $c_{i 2} = 1$ c_{i2} = 1 if $i < n$ i < n and $p_{i} = p_{i + 1}$ p_i = p_{i + 1}, otherwise $c_{i 2} = 0$ c_{i2} = 0.

If $i = 1$ i = 1 or $i = n$ i = n, the element has only one neighbor. Otherwise, the element has two neighbors.

After you have determined the answer, you need to output:

After that, your program should terminate.

Input

First, your program should read one integer $n$ $(1 \leq n \leq 2 \cdot 1 0^{3})$ (1 \le n \le 2 \cdot 10^3) — the length of the hidden array.

The array $a$ $(1 \leq a_{i} \leq 1 0^{6})$ (1 \le a_i \le 10^6) is not given to your program.

First, your program should read one integer $n$ — the length of the hidden array.

To make a query, output:

? $j_{1}$ j_1 $j_{2}$ j_2 $\dots$ $j_{n}$ j_n, where $j_{1}, j_{2}, \dots, j_{n}$ j_1, j_2, \ldots, j_n is a permutation of the numbers from $1$ to $n$ .

After each such query, your program should read $n$ integers $b_{1}, b_{2}, \dots, b_{n}$ b_1, b_2, \ldots, b_n — the answer to the query.

When you have determined the answer, output:

! $an s$ , where $an s$ is the number of distinct numbers in the hidden array $a$ .

After outputting the answer, your program should terminate.

After each output, you need to flush the output buffer.

In C++, this can be done as follows:

cout << endl;

or like this:

cout.flush();

The final output ! $an s$ does not count as a query.

If your program makes an invalid query or exceeds the query limit, it will receive the Wrong Answer verdict.

Example 1