A ticketing service stores distinct fares in a binary search tree. Starting from an empty tree, the fares are inserted one at a time in the order given (standard BST insertion: go left when the new fare is smaller than the current node, otherwise go right). Given an inclusive band [lo, hi] and an index k, consider only the stored fares that lie within [lo, hi], sorted ascending, and report the k-th of them.
Input format
Line 1: an integer n, the number of fares.
Line 2: n space-separated distinct integers, the fares in insertion order.
Line 3: three space-separated integers lo, hi, and k with lo <= hi and k >= 1.
Output format
A single integer: the k-th smallest fare within [lo, hi]. If fewer than k fares lie within the band, print NONE.
Constraints
- 1 <= n <= 40
- 1 <= k <= n
- All fares are distinct, each with absolute value <= 1000000.
- -2000000 <= lo <= hi <= 2000000