Kth Largest Element Using Counting Sort

You are given an array of integers and an integer \(K\). Your task is to find the \(K\)th largest element in the array using the counting sort algorithm. Counting sort is efficient when the range of input data is not significantly greater than the number of objects to be sorted. The algorithm works by counting the number of objects that have each distinct key value, and doing some arithmetic to calculate the positions of each key value in the output sequence.

Formally, if the sorted array in ascending order is \(a_1, a_2, \ldots, a_N\), then the \(K\)th largest element is \(a_{N-K+1}\). You are required to implement this using the counting sort approach.

inputFormat

The input is given via stdin as follows:

1. The first line contains a single integer \(N\), the number of elements in the array.
2. The second line contains \(N\) space-separated integers representing the elements of the array.
3. The third line contains the integer \(K\), indicating that you need to find the \(K\)th largest element.

outputFormat

Output the \(K\)th largest element in the array to stdout.

## sample

6
3 2 1 5 6 4
2

5

</p>