Inorder Successor in a BST

Source: Phuoc Hung OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Build a BST from $a_1,a_2,\ldots,a_n$ in insertion order. Duplicate insertion keys are ignored.

A key $x$ is guaranteed to exist in the tree. The strict inorder successor of $x$ is the smallest stored key that is greater than $x$.

Find this strict inorder successor. If no stored key is greater than $x$, the successor does not exist.

Input

The first line contains $n$.

The second line contains $n$ signed integers $a_1,a_2,\ldots,a_n$ in insertion order.

The third line contains $x$.

Output

Print the successor key if it exists; otherwise print NONE.

Subtasks

Subtask 1 (20 points): $1\le n\le 20$.

Subtask 2 (30 points): $1\le n\le 5000$.

Subtask 3 (50 points): $1\le n\le 200000$.

In all subtasks, $a_i$ and $x$ are signed 64-bit integers, duplicate insertion keys are ignored, and $x$ is guaranteed to belong to the resulting BST.

Examples

Input

7
8 3 10 1 6 14 4
6

Output

8

Explanation

The stored keys greater than $6$ are $8,10,14$. The smallest of them is $8$, so the strict inorder successor of $6$ is $8$.