A pricing service stores distinct tariff amounts in a binary search tree. Starting from an empty tree, the amounts are inserted one at a time in the order given (standard BST insertion: go left when the new amount is smaller than the current node, otherwise go right). After all insertions, report the k-th smallest tariff stored in the tree.
Input format
Line 1: an integer n, the number of tariffs.
Line 2: n space-separated distinct integers, the tariffs in insertion order.
Line 3: an integer k.
Output format
A single integer: the k-th smallest tariff (1-indexed, so k = 1 is the minimum).
Constraints
- 1 <= n <= 40
- 1 <= k <= n
- All tariffs are distinct, each with absolute value <= 1000000.