Liệt kê lá theo thứ tự giảm dần (List BST Leaves in Descending Order)

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

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

Đề bài

Dựng BST từ dãy $a_1,a_2,\ldots,a_n$ theo đúng thứ tự chèn; khóa trùng bị bỏ qua.

Một nút được gọi là nút lá nếu nút đó không có con trái và cũng không có con phải. Trong cây chỉ có một nút, nút gốc đồng thời là một nút lá.

Hãy lấy khóa của tất cả các nút lá và in chúng theo thứ tự giảm dần.

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$, dòng này không xuất hiện.

Output

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

Nếu cây rỗng và do đó không có nút lá, 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

14 4 1

Giải thích

Trong cây thu được, các nút mang khóa $1$, $4$ và $14$ đều không có con trái lẫn con phải, nên đây chính là ba nút lá. Các nút còn lại đều có ít nhất một nút con.

Ba khóa lá là $1,4,14$. Sắp chúng theo thứ tự giảm dần ta được $14,4,1$, vì vậy chương trình in 14 4 1.