Problems
Медіанне божевілля
Медіанне божевілля
\textit{Це інтерактивна задача.}
Загадана деяка перестановка $p$ чисел від $1$ до $n$, де $n$ \textbf{парне}. Ви можете задавати запити наступного вигляду:
\begin{itemize}
\item
Для даного набору різних індексів непарної довжини $a_1, a_2, \dots, a_l$, ви можете дізнатись таке число $x$, що $p_x$ є медіаною елементів $p_{a_1}, p_{a_2}, \dots, p_{a_l}$.
\end{itemize}
\textbf{Відомо, що $p_1<p_n$}. Вгадайте перестановку $p$ за \textbf{не більше ніж $\frac{3n}{2}$} запитів.
Гарантується, що перестановка зафіксована перед початком взаємодії. Іншими словами, \textbf{інтерактор не адаптивний}.
Нагадаємо, що медіана непарної кількості чисел визначається наступним чином:
Нехай $b_1, b_2, \ldots, b_{2k+1}$ --- це ці числа в порядку зростання (де $2k+1$ --- кількість чисел). Тоді медіаною є число $b_{k+1}$.
\Interaction
Почніть взаємодію, зчитавши одне ціле число $n$ ($2 \le n \le 1000$, $n$ парне) --- довжину перестановки.
Щоб задати питання, необхідно вивести в одному рядку спочатку символ <<\t{?}>>, потім ціле число $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}$.
Коли ви визначили перестановку, то виведіть спочатку символ <<\t{!}>>, а потім $n$ чисел $p_1, p_2, \ldots, p_n$. Після цього ваша програма має завершити роботу.
Після кожного запиту і виводу відповіді не забудьте вивести перехід рядка і скинути буфер виводу. Для скидання буферу використовуйте:
\begin{itemize}
\item \texttt{fflush(stdout)} чи \texttt{cout.flush()} в C++;
\item \texttt{System.out.flush()} в Java;
\item \texttt{flush(output)} в Pascal;
\item \texttt{stdout.flush()} в Python;
\end{itemize}
\Note
В прикладі загадана перестановка $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$.
Input example #1
4 1 3 2 4
Output example #1