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.
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.
A single integer: the k-th smallest fare within [lo, hi]. If fewer than k fares lie within the band, print NONE.
Example 1
Input
7 40 20 60 10 30 50 70 25 65 2
Expected
40
Explanation
Fares within [25, 65] sorted ascending are 30, 40, 50, 60. The 2nd of them is 40.
Example 2
Input
5 5 2 8 1 9 1 3 5
Expected
NONE
Explanation
Fares within [1, 3] are 1 and 2, only two of them. Since k = 5 exceeds 2, the answer is NONE.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →