Đây là một bài toán tương tác.

Có một hoán vị ẩn $p_1, p_2, \dots, p_n$ của $\{1, 2, \dots, n\}$. Bạn cần tìm hoán vị này bằng cách hỏi tính chẵn lẻ của số lượng nghịch thế trong đoạn $p_l, \dots, p_r$.

Bạn có thể truy vấn theo định dạng "? l r", và bộ tương tác sẽ trả về $(\sum_{l \le i < j \le r} [p_i > p_j]) \pmod 2$. Trong đó $[p_i > p_j]$ bằng 1 nếu $p_i > p_j$ và bằng 0 nếu $p_i \le p_j$.

Giao thức tương tác

Đầu tiên, bạn cần đọc số nguyên $n$ ($1 \le n \le 2000$).

Sau đó, bạn có thể thực hiện không quá $4 \times 10^4$ truy vấn. Để thực hiện một truy vấn, hãy in ra "? l r" ($1 \le l \le r \le n$) trên một dòng riêng biệt, sau đó đọc phản hồi từ đầu vào chuẩn.

Để đưa ra câu trả lời, hãy in ra "! $p_1$ $p_2$ $\dots$ $p_n$" trên một dòng riêng biệt. Việc in câu trả lời không được tính vào giới hạn $4 \times 10^4$ truy vấn.

Sau đó, chương trình của bạn phải kết thúc.

Sau khi in một truy vấn, đừng quên in ký tự xuống dòng và đẩy dữ liệu ra (flush). Để làm điều này, hãy sử dụng fflush(stdout) hoặc cout.flush() trong C++, System.out.flush() trong Java, flush(output) trong Pascal, hoặc stdout.flush() trong Python.

Đảm bảo rằng hoán vị đã được cố định từ trước.

Ví dụ

Dữ liệu vào 1

3
0
0
1

Dữ liệu ra 1

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