Kth Smallest Element in BST

Mediumjavapythonccppjavascript

Given a Binary Search Tree and an integer K, find the K-th smallest value (1-indexed).

Input Format

The first line contains an integer M. The second line contains M space-separated tokens (integers or null) — the BST in level order. The third line contains the integer K.

Output Format

Print the K-th smallest value.

Example 1

Input

7
5 3 7 2 4 6 8
3

Output

Explanation: The in-order values are 2 3 4 5 6 7 8; the third is 4.

Input (stdin)

Output

Run your code to see output here...