これはインタラクティブな問題です。

$\{1, 2, \dots, n\}$ の隠された順列 $p_1, p_2, \dots, p_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]$ は $p_i > p_j$ のときに $1$、$p_i \le p_j$ のときに $0$ となる値です。

インタラクション

まず、整数 $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$ 回のクエリ制限には含まれません。

その後、プログラムを終了してください。

クエリを出力した後は、必ず改行を出力し、出力をフラッシュしてください。これを行うには、C++ では fflush(stdout) または cout.flush() を、Java では System.out.flush() を、Pascal では flush(output) を、Python では stdout.flush() を使用してください。

順列はあらかじめ固定されていることが保証されています。

入出力例

入力 1

3
0
0
1

出力 1

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