Il existe une permutation cachée $p_1, p_2, \dots, p_n$ de $\{1, 2, \dots, n\}$. Vous souhaitez la trouver en demandant la parité du nombre d'inversions de $p_l, \dots, p_r$.

Vous pouvez effectuer des requêtes sous la forme « ? $l$ $r$ », et l'interacteur vous répondra $\left(\sum_{l \le i < j \le r} [p_i > p_j]\right) \pmod 2$. $[p_i > p_j]$ vaut 1 si $p_i > p_j$ et 0 si $p_i \le p_j$.

Protocole d'interaction

Tout d'abord, vous devez lire l'entier $n$ ($1 \le n \le 2000$).

Ensuite, vous pouvez effectuer au plus $4 \times 10^4$ requêtes. Pour effectuer une requête, affichez « ? $l$ $r$ » ($1 \le l \le r \le n$) sur une ligne séparée, puis lisez la réponse depuis l'entrée standard.

Pour donner votre réponse, affichez « ! $p_1$ $p_2$ $\dots$ $p_n$ » sur une ligne séparée. L'affichage de la réponse n'est pas comptabilisé dans la limite de $4 \times 10^4$ requêtes.

Après cela, votre programme doit se terminer.

Après avoir affiché une requête, n'oubliez pas d'afficher un saut de ligne et de vider le tampon de sortie (flush). Pour ce faire, utilisez fflush(stdout) ou cout.flush() en C++, System.out.flush() en Java, flush(output) en Pascal, ou stdout.flush() en Python.

Il est garanti que la permutation est fixée à l'avance.

Exemples

Entrée 1

3
0
0
1

Sortie 1

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