Lowest Common Ancestor of a Binary Search Tree

Source: LeetCode

Version: Phuoc Hung OJ Extended

Problem Statement

Build a BST from the $n$ distinct keys $a_1,a_2,\ldots,a_n$ in insertion order.

Two different keys $p$ and $q$ are guaranteed to exist. A node $u$ is a common ancestor of $p$ and $q$ if both target nodes lie in the subtree rooted at $u$. A node is allowed to be a descendant of itself.

The lowest common ancestor (LCA) is the common ancestor with maximum depth, i.e. the lowest such node in the tree.

Print the key stored at the LCA of $p$ and $q$.

Input

The first line contains $n$.

The second line contains the $n$ distinct keys $a_1,a_2,\ldots,a_n$ in insertion order.

The third line contains $p$ and $q$.

Output

Print one integer: the key of the LCA of $p$ and $q$.

Subtasks

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

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

Subtask 3 (50 points): $2\le n\le 10^5$.

In all subtasks, $-10^9\le a_i,p,q\le 10^9$, all $a_i$ are distinct, $p\ne q$, and both $p$ and $q$ occur in the tree.

Examples

Input

9
6 2 8 0 4 7 9 3 5
2 8

Output

6

Explanation

Key $2$ lies in the left subtree of root $6$, while key $8$ lies in its right subtree. No node below $6$ can have both targets in its subtree.

Therefore their LCA has key $6$.