Find the K-th Largest Element

You are given an array of integers and an integer ( k ). Your task is to find the ( k )-th largest element in the array. This means that when the array is sorted in descending order, you need to return the element that appears in the ( k )-th position. Use a randomized quickselect algorithm to solve this problem efficiently.

inputFormat

Input is given via stdin. The first line contains an integer ( n ) representing the number of elements in the array. The second line contains ( n ) space-separated integers. The third line contains an integer ( k ) indicating which largest element to find.

outputFormat

Output the ( k )-th largest element as a single integer to stdout.## sample

6
3 2 1 5 6 4
2

5