Существует скрытая перестановка $p_1, p_2, \dots, p_n$ чисел $\{1, 2, \dots, n\}$. Вам нужно найти её, запрашивая чётность количества инверсий в подпоследовательности $p_l, \dots, p_r$.

Вы можете делать запросы в формате «? $l$ $r$», и интерактор ответит вам значением $(\sum_{l \le i < j \le r} [p_i > p_j]) \pmod 2$. $[p_i > p_j]$ равно $1$, если $p_i > p_j$, и $0$, если $p_i \le p_j$.

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

Сначала вы должны считать целое число $n$ ($1 \le n \le 2000$).

После этого вы можете сделать не более $4 \times 10^4$ запросов. Чтобы сделать запрос, выведите «? $l$ $r$» ($1 \le l \le r \le n$) на отдельной строке, после чего считайте ответ из стандартного потока ввода.

Чтобы вывести ответ, выведите «! $p_1$ $p_2$ $\dots$ $p_n$» на отдельной строке. Вывод ответа не учитывается в ограничении на $4 \times 10^4$ запросов.

После этого ваша программа должна завершиться.

После вывода запроса не забудьте вывести символ переноса строки и очистить буфер вывода. Для этого используйте fflush(stdout) или cout.flush() в C++, System.out.flush() в Java, flush(output) в Pascal или stdout.flush() в Python.

Гарантируется, что перестановка зафиксирована заранее.

Пример

Входные данные 1

3
0
0
1

Выходные данные 1

? 1 2
? 1 3
? 2 3
! 2 3 1