這是一個互動式問題。

有一個隱藏的排列 $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]$ 在 $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$)，然後從標準輸入讀取回應。

若要給出你的答案，請在獨立的一行輸出 ! p1 p2 ... pn。輸出答案的次數不計入 $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