Predecessor trong BST (Inorder Predecessor in a BST)

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; nếu một khóa đã có trong cây thì lần chèn lặp lại bị bỏ qua.

Cho một khóa $x$ được bảo đảm tồn tại trong cây. Inorder predecessor nghiêm ngặt của $x$ là khóa lớn nhất trong BST có giá trị nhỏ hơn $x$.

Hãy tìm inorder predecessor nghiêm ngặt của $x$. Nếu không có khóa nào nhỏ hơn $x$, predecessor không tồn tại.

Input

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

Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$ theo thứ tự chèn.

Dòng thứ ba chứa số nguyên $x$.

Output

Nếu predecessor của $x$ tồn tại, in khóa đó.

Nếu không tồn tại, in NONE.

Subtask

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

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

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

Trong tất cả các subtask, $a_i$ và $x$ là số nguyên có dấu 64-bit; khóa trùng bị bỏ qua khi dựng cây và $x$ được bảo đảm thuộc tập khóa còn lại của BST.

Ví dụ

Input

7
8 3 10 1 6 14 4
6

Output

4

Giải thích

Các khóa nhỏ hơn $6$ trong cây là $1,3,4$. Trong số đó, khóa lớn nhất là $4$. Vì vậy inorder predecessor nghiêm ngặt của $6$ là $4$.