Find the k-th Largest Element

Given an unsorted list of integers, your task is to find the k-th largest element. The k-th largest element is defined as the element that would appear in the sorted order (in non-decreasing order) at index \(n-k\), where \(n\) is the number of elements. For example, if \(n=6\) and \(k=2\), you should find the element at index \(6-2=4\) (0-indexed) when the array is sorted.

Your solution must use an algorithm with expected linear time complexity. A common method to achieve this is the Quickselect algorithm. Recall that the partition process in Quickselect rearranges the array such that all elements less than a chosen pivot come before it and all elements greater come after it.

inputFormat

Input is given via stdin in the following format:
The first line contains an integer \(n\), the number of elements in the array.
The second line contains \(n\) space-separated integers, representing the array elements.
The third line contains an integer \(k\), indicating that you need to find the k-th largest element.

outputFormat

Output the k-th largest element to stdout.

6
3 2 1 5 6 4
2

5