Медіанне божевілля#10765

Медіанне божевілля

3 seconds

256 megabytes

Very easy

Це інтерактивна задача.

Загадана деяка перестановка $p$ чисел від $1$ до $n$ , де $n$ парне. Ви можете задавати запити наступного вигляду:

Для даного набору різних індексів непарної довжини $a_{1}, a_{2}, \dots, a_{l}$ a_1, a_2, \dots, a_l, ви можете дізнатись таке число $x$ , що $p_{x}$ p_x є медіаною елементів $p_{a_{1}}, p_{a_{2}}, \dots, p_{a_{l}}$ p_{a_1}, p_{a_2}, \dots, p_{a_l}.

Відомо, що $p_{1} < p_{n}$ p_1<p_n. Вгадайте перестановку $p$ за не більше ніж $\frac{3 n}{2}$ \frac{3n}{2} запитів.

Гарантується, що перестановка зафіксована перед початком взаємодії. Іншими словами, інтерактор не адаптивний.

Нагадаємо, що медіана непарної кількості чисел визначається наступним чином:

Нехай $b_{1}, b_{2}, \dots, b_{2 k + 1}$ b_1, b_2, \ldots, b_{2k+1} — це ці числа в порядку зростання (де $2 k + 1$ 2k+1 — кількість чисел). Тоді медіаною є число $b_{k + 1}$ b_{k+1}.

Input

Почніть взаємодію, зчитавши одне ціле число $n$ ( $2 \leq n \leq 1000$ 2 \le n \le 1000, $n$ парне) — довжину перестановки.

Interaction

Щоб задати питання, необхідно вивести в одному рядку спочатку символ «?», потім ціле число $l$ , а потім $l$ цілих чисел $a_{i}$ a_i ( $1 \leq l \leq n$ 1 \le l \le n, $1 \leq a_{i} \leq n$ 1 \le a_i \le n, $l$ непарне, всі $a_{i}$ a_i попарно різні) — індекси, для яких необхідно знайти медіану.

У відповідь програма журі виведе таке число $x$ , що $p_{x}$ p_x є медіаною елементів $p_{a_{1}}, p_{a_{2}}, \dots, p_{a_{l}}$ p_{a_1}, p_{a_2}, \dots, p_{a_l}.

Коли ви визначили перестановку, то виведіть спочатку символ «!», а потім $n$ чисел $p_{1}, p_{2}, \dots, p_{n}$ p_1, p_2, \ldots, p_n. Після цього ваша програма має завершити роботу.

Після кожного запиту і виводу відповіді не забудьте вивести перехід рядка і скинути буфер виводу. Для скидання буферу використовуйте:

fflush(stdout) чи cout.flush() в C++;
System.out.flush() в Java;
flush(output) в Pascal;
stdout.flush() в Python;

Examples

Example 1

Note

В прикладі загадана перестановка $p = (1, 3, 2, 4)$ p = (1, 3, 2, 4).

Перший запит в прикладі — хочемо дізнатись медіану елементів $p_{2}, p_{3}, p_{4}$ p_2, p_3, p_4, що дорівнюють $3, 2, 4$ відповідно. Медіана цих чисел — $3$ , тобто $p_{2}$ p_2, тому інтерактор відповідає числом $2$ .

Другий запит в прикладі — хочемо дізнатись медіану елементів $p_{1}, p_{3}, p_{4}$ p_1, p_3, p_4, що дорівнюють $1, 2, 4$ відповідно. Медіана цих чисел — $2$ , тобто $p_{3}$ p_3, тому інтерактор відповідає числом $3$ .

Третій запит в прикладі — хочемо дізнатись медіану елементів $p_{1}, p_{2}, p_{4}$ p_1, p_2, p_4, що дорівнюють $1, 3, 4$ відповідно. Медіана цих чисел — $3$ , тобто $p_{2}$ p_2, тому інтерактор відповідає числом $2$ .

Четвертий запит в прикладі — хочемо дізнатись медіану елементів $p_{1}, p_{2}, p_{3}$ p_1, p_2, p_3, що дорівнюють $1, 3, 2$ відповідно. Медіана цих чисел — $2$ , тобто $p_{3}$ p_3, тому інтерактор відповідає числом $3$ .