Successor trong BST (Inorder Successor 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 successor nghiêm ngặt của $x$ là khóa nhỏ nhất trong BST có giá trị lớn hơn $x$.

Hãy tìm inorder successor nghiêm ngặt của $x$. Nếu không có khóa nào lớn hơn $x$, successor 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 successor 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

8

Giải thích

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