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

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

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

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

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

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

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

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

Протокол взаимодействия

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

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

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

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

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

• fflush(stdout) чи cout.flush() в C++;

• System.out.flush() в Java;

• flush(output) в Pascal;

• stdout.flush() в Python;

Примеры

Примечание

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

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

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

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

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