You are given an array of n integers and an integer k. Print the k-th largest value.
The k-th largest value is defined positionally: sort the array in non-increasing order; the answer is the element at position k (1-indexed). Duplicates are not removed, so, for example, in [5, 5, 4] the 1st and 2nd largest are both 5 and the 3rd largest is 4. This makes the answer unique.
Input format
Line 1: two space-separated integers n and k.
Line 2: n space-separated integers, the array values.
Output format
A single integer: the k-th largest value.
Constraints
- 1 ≤ k ≤ n ≤ 100000
- -1000000000 ≤ each value ≤ 1000000000