Print the k-th largest value in the array (counting duplicates: in 5 5 4, the 2nd largest is 5).
Constraints
- 1 ≤ k ≤ n ≤ 200000
- −10^9 ≤ values ≤ 10^9
Input and output
- Input
- Line 1: n k Line 2: n integers
- Output
- One integer.
Examples
Input 1
6 2
3 2 1 5 6 4Output
55
Input 2
3 2
5 5 4Output
5Duplicates count.
Show hints
- Keep only the k largest values seen so far.
Show the explanation
Keep a min-heap of size k: push each value, and if the heap grows past k, pop the smallest. After all values, the top of the heap is the k-th largest. O(n log k) time, O(k) space. Sorting (O(n log n)) or quickselect (O(n) on average) are valid alternatives worth comparing out loud.
Original UniCircle question. Last reviewed 21 Oct 2026.