Inorder Predecessor 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 predecessor of $x$ is the largest stored key that is smaller than $x$.

Find this strict inorder predecessor. If no stored key is smaller than $x$, the predecessor 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 predecessor 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

4

Explanation

The stored keys smaller than $6$ are $1,3,4$. The largest of them is $4$, so the strict inorder predecessor of $6$ is $4$.