A store keeps its distinct price points in a binary search tree. Starting from an empty tree, the prices are inserted one at a time in the order given (standard BST insertion: go left when the new price is smaller than the current node, otherwise go right). Given a budget, report the floor of the budget: the largest stored price that is less than or equal to budget.
Input format
Line 1: an integer n, the number of prices.
Line 2: n space-separated distinct integers, the prices in insertion order.
Line 3: an integer budget.
Output format
A single integer: the largest stored price <= budget. If no stored price is <= budget, print NONE.
Constraints
- 1 <= n <= 40
- All prices are distinct, each with absolute value <= 1000000.
- -2000000 <= budget <= 2000000