Bạn được cho một dãy gồm \(n\) số \(x_1,x_2,\ldots,x_n\). Mỗi số \(1,2,\ldots,n\) xuất hiện đúng một lần trong dãy.

Bạn có thể thay đổi dãy bằng các phép đổi chỗ. Có \(n-1\) lượt liên tiếp, được đánh số \(k=2,3,\ldots,n\). Ở lượt \(k\), bạn có thể đổi chỗ hai giá trị \(x_k\) và \(x_{\lfloor k/2 \rfloor}\) trong dãy hoặc không làm gì.

Dãy \(a_1,a_2,\ldots,a_n\) nhỏ hơn dãy \(b_1,b_2,\ldots,b_n\) theo thứ tự từ điển nếu tồn tại một chỉ số \(j\) (\(1 \le j \le n\)) sao cho \(a_k=b_k\) với mọi \(k<j\) và \(a_j<b_j\).

Hãy tìm dãy nhỏ nhất theo thứ tự từ điển mà bạn có thể thu được.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\).

Dòng thứ hai chứa \(n\) số nguyên: các số trong dãy.

Dữ liệu ra

In ra \(n\) số nguyên biểu diễn dãy nhỏ nhất theo thứ tự từ điển có thể thu được.

Phân nhóm

1. Nhóm 1 (10 điểm): \(1 \le n \le 20\).
2. Nhóm 2 (11 điểm): \(1 \le n \le 40\).
3. Nhóm 3 (27 điểm): \(1 \le n \le 1000\).
4. Nhóm 4 (20 điểm): \(1 \le n \le 5 \cdot 10^4\).
5. Nhóm 5 (32 điểm): \(1 \le n \le 2 \cdot 10^5\).

Ví dụ

5
3 4 2 5 1

2 1 3 4 5

Nguồn

Baltic Olympiad in Informatics 2016, ngày thi thứ hai, bài C.