Kth Largest Element in a Binary Search Tree

You are given a sequence of integers that should be inserted into a Binary Search Tree (BST) in the given order. Your task is to find the kth largest element in the BST. The kth largest element is defined as the element which is larger than exactly k-1 other elements in the tree. Mathematically, if the in-order traversal of the BST produces a sorted array \(A\), then the kth largest element is \(A[\text{length}(A)-k]\).

Note: The BST is constructed by inserting the nodes one by one in the order provided. Duplicate values will be inserted to the right subtree.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains two integers n and k, where n is the number of nodes and k denotes which largest element to find.
2. The second line contains n space-separated integers representing the values of the nodes to be inserted into the BST in order.

outputFormat

Output a single integer to standard output (stdout): the kth largest element in the BST.

4 2
3 1 4 5

4