Tý muốn kiểm tra tính chất quan trọng nhất của BST: phép duyệt inorder cho ra dãy tăng dần. Tý sẽ tạo một BST từ một dãy số và muốn xem kết quả duyệt inorder của cây.

Hãy giúp Tý viết chương trình in ra kết quả duyệt inorder của BST.

Định dạng đầu vào

• Dòng đầu chứa số nguyên dương \(N\) (\(1 \le N \le 10^3\)).
• Dòng thứ hai chứa \(N\) số nguyên dương phân biệt \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).

Định dạng đầu ra

• In ra một dòng chứa \(N\) số là kết quả duyệt inorder của BST, các số cách nhau bởi một khoảng trắng.

Ví dụ

Input:

7
5 3 7 2 4 6 8

Output:

2 3 4 5 6 7 8

Giải thích: Duyệt inorder của BST cho dãy tăng dần \([2, 3, 4, 5, 6, 7, 8]\).

Ràng buộc & Subtasks