An inventory index is a binary search tree keyed by distinct integer SKU codes. Starting from an empty tree, the codes are inserted one at a time in the order given (standard BST insertion: go left when the new code is smaller than the current node, otherwise go right); this determines the tree's shape. Given an inclusive band [lo, hi], consider the set of all nodes whose code lies within [lo, hi] and report the code at their lowest common ancestor (the deepest node that is an ancestor of every in-band node; a node is an ancestor of itself).
Input format
Line 1: an integer n, the number of SKU codes.
Line 2: n space-separated distinct integers, the codes in insertion order.
Line 3: two space-separated integers lo and hi with lo <= hi.
Output format
A single integer: the code at the lowest common ancestor of all in-band nodes. If no node lies within [lo, hi], print NONE.
Constraints
- 1 <= n <= 40
- All codes are distinct, each with absolute value <= 1000000.
- -2000000 <= lo <= hi <= 2000000