Giá trị nhỏ nhất và lớn nhất (Minimum and Maximum in a BST)

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

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

Đề bài

Ban đầu BST rỗng. Chèn lần lượt các khóa $a_1,a_2,\ldots,a_n$ theo quy tắc của cây tìm kiếm nhị phân: khóa nhỏ hơn đi sang trái, khóa lớn hơn đi sang phải; khi gặp vị trí rỗng thì tạo nút mới. Nếu một khóa đã tồn tại, lần chèn lặp lại bị bỏ qua.

Sau khi dựng cây, hãy xác định khóa nhỏ nhất và khóa lớn nhất đang có trong BST.

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

Nếu cây rỗng, in:

EMPTY

Ngược lại, in hai số trên một dòng: khóa nhỏ nhất trước, khóa lớn nhất sau.

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

1 14

Giải thích

Sau khi chèn toàn bộ dãy, các khóa hiện có là $\{1,3,4,6,8,10,14\}$. Giá trị nhỏ nhất là $1$ và giá trị lớn nhất là $14$, nên chương trình in 1 14.