Duyệt inorder của BST (BST Inorder Traversal)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Dựng một cây tìm kiếm nhị phân (BST) từ dãy $a_1,a_2,\ldots,a_n$ theo đúng thứ tự chèn. Khi chèn, khóa nhỏ hơn khóa tại nút hiện tại đi sang con trái, khóa lớn hơn đi sang con phải; khóa đã tồn tại bị bỏ qua.

Sau khi cây được dựng xong, thực hiện duyệt inorder. Với một nút, thứ tự inorder là: duyệt toàn bộ cây con trái, thăm nút hiện tại, rồi duyệt toàn bộ cây con phải.

Hãy in các khóa theo đúng thứ tự được thăm.

Input

Dòng đầu chứa số nguyên $n$.

Nếu $n>0$, dòng tiếp theo chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$. Nếu $n=0$, dòng này không xuất hiện.

Output

Nếu cây có ít nhất một nút, in dãy khóa theo thứ tự inorder trên một dòng, các khóa cách nhau bởi một dấu cách.

Nếu cây rỗng, in EMPTY.

Subtask

Subtask 1 (20 điểm): $0\le n\le 20$.

Subtask 2 (30 điểm): $0\le n\le 5000$.

Subtask 3 (50 điểm): $0\le n\le 200000$.

Trong tất cả các subtask, $-2^{63}\le a_i\le 2^{63}-1$. Khóa trùng bị bỏ qua khi dựng cây.

Ví dụ

Input

7
8 3 10 1 6 14 4

Output

1 3 4 6 8 10 14

Giải thích

Cây được dựng từ đúng thứ tự chèn trong input. Khi duyệt inorder, các nút của cây này được thăm lần lượt với khóa $1,3,4,6,8,10,14$, vì vậy output là dãy trên.