Find the k-th Smallest Element in a Binary Search Tree

Given the preorder traversal of a Binary Search Tree (BST) and an integer ( k ), construct the BST and determine the ( k )-th smallest element in the BST. The BST is constructed by inserting nodes in the order given by the preorder traversal. Recall that in a BST, for any given node, all nodes in its left subtree are less than the node and all nodes in its right subtree are greater. This problem requires that you output the ( k )-th smallest element (i.e., the element that appears in the ( k )-th position in the sorted order of the BST elements).

inputFormat

The input is given via standard input (stdin) and consists of three lines:

1. The first line contains an integer ( n ) representing the number of nodes in the BST.
2. The second line contains ( n ) space-separated integers representing the preorder traversal of the BST.
3. The third line contains an integer ( k ), where ( 1 \leq k \leq n ), indicating that you need to find the ( k )-th smallest element in the BST.

outputFormat

Output the ( k )-th smallest element in the BST to standard output (stdout).## sample

4
3 1 2 4
2

2