To jest zadanie interaktywne.

Istnieje ukryta permutacja $p_1, p_2, \dots, p_n$ zbioru $\{1, 2, \dots, n\}$. Twoim celem jest odnalezienie jej poprzez pytania o parzystość liczby inwersji w podciągu $p_l, \dots, p_r$.

Możesz zadawać pytania w formacie "? l r", a interaktor odpowie wartością $(\sum_{l \le i < j \le r} [p_i > p_j]) \pmod 2$. $[p_i > p_j]$ wynosi 1, gdy $p_i > p_j$, oraz 0, gdy $p_i \le p_j$.

Protokół interakcji

Najpierw należy wczytać liczbę całkowitą $n$ ($1 \le n \le 2000$).

Następnie możesz zadać nie więcej niż $4 \times 10^4$ pytań. Aby zadać pytanie, wypisz "? l r" ($1 \le l \le r \le n$) w osobnej linii, a następnie wczytaj odpowiedź ze standardowego wejścia.

Aby podać odpowiedź, wypisz "! $p_1$ $p_2$ $\dots$ $p_n$" w osobnej linii. Wypisanie odpowiedzi nie wlicza się do limitu $4 \times 10^4$ pytań.

Po wypisaniu odpowiedzi program powinien się zakończyć.

Po wypisaniu zapytania nie zapomnij wypisać znaku końca linii i opróżnić bufora wyjściowego. Aby to zrobić, użyj fflush(stdout) lub cout.flush() w C++, System.out.flush() w Javie, flush(output) w Pascalu lub stdout.flush() w Pythonie.

Gwarantuje się, że permutacja jest ustalona z góry.

Przykład

Wejście 1

3
0
0
1

Wyjście 1

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