An org chart is stored as a binary search tree keyed by distinct integer employee ids. Starting from an empty tree, the ids are inserted one at a time in the order given (standard BST insertion: go left when the new id is smaller than the current node, otherwise go right); this insertion order determines the tree's shape. Given two distinct ids u and v, both guaranteed to be present, report the id at their lowest common ancestor (the deepest node that has both u and v in its subtree; a node is considered to be in its own subtree).
Input format
Line 1: an integer n, the number of ids.
Line 2: n space-separated distinct integers, the ids in insertion order.
Line 3: two space-separated distinct integers u and v, both present in the tree.
Output format
A single integer: the id stored at the lowest common ancestor of u and v.
Constraints
- 2 <= n <= 40
- All ids are distinct, each with absolute value <= 1000000.
uandvare distinct and both appear among the ids.