Chèn dãy khóa vào BST (Insert a Key Sequence into a BST)

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

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

Đề bài

Ban đầu có một cây tìm kiếm nhị phân (BST) rỗng. Với mỗi khóa $a_i$ theo thứ tự từ $a_1$ đến $a_n$, thực hiện chèn như sau:

• Nếu cây đang rỗng, khóa được chèn trở thành gốc.
• Tại một nút có khóa $v$, nếu $a_i<v$ thì tiếp tục sang con trái; nếu $a_i>v$ thì tiếp tục sang con phải.
• Khi nhánh cần đi tới đang rỗng, tạo nút mới mang khóa $a_i$ tại đó.
• Nếu $a_i=v$ tại một nút đã có, bỏ qua lần chèn này; BST không lưu thêm một bản sao của khóa trùng.

Sau khi xử lý toàn bộ dãy, hãy mô tả cấu trúc cây bằng hai phép duyệt:

• preorder: thăm gốc, sau đó cây con trái, rồi cây con phải;
• inorder: thăm cây con trái, sau đó gốc, rồi cây con phải.

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$ theo thứ tự chèn. Nếu $n=0$, không có dòng chứa dãy khóa.

Output

Dòng thứ nhất in dãy khóa thu được khi duyệt preorder.

Dòng thứ hai in dãy khóa thu được khi duyệt inorder.

Các khóa trên cùng một dòng được cách nhau bởi một dấu cách. Nếu cây rỗng, in EMPTY trên cả hai dòng.

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, mỗi $a_i$ là số nguyên có dấu 64-bit: $-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

8 3 1 6 4 10 14
1 3 4 6 8 10 14

Giải thích

Khóa $8$ là gốc. Các khóa $3$ và $10$ lần lượt trở thành con trái và con phải của $8$; tiếp tục chèn các khóa còn lại tạo ra đúng một BST theo thứ tự đầu vào.

Duyệt preorder thăm gốc trước nên bắt đầu bằng $8$, rồi lần lượt cho dãy 8 3 1 6 4 10 14. Duyệt inorder thăm trái - gốc - phải nên cho dãy 1 3 4 6 8 10 14.