You are given a sequence of integers of length \(n\) and integer number \(k\). You should print any integer number \(x\) in the range of \([1; 10^9]\) (i.e. \(1 \le x \le 10^9\)) such that exactly \(k\) elements of given sequence are less than or equal to \(x\).
Note that the sequence can contain equal elements.
If there is no such \(x\), print "-1" (without quotes).
Input
The first line of the input contains integer numbers \(n\) and \(k\) (\(1 \le n \le 2 \cdot 10^5\), \(0 \le k \le n\)).
The second line of the input contains \(n\) integer numbers \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) --- the sequence itself.
Output
Print any integer number \(x\) from range \([1; 10^9]\) such that exactly \(k\) elements of given sequence is less or equal to \(x\).
If there is no such \(x\), print "-1" (without quotes).
Example
Test 1
Input
7 4
3 7 5 1 10 3 20Output
Note
In the first example \(5\) is also a valid answer because the elements with indices \([1, 3, 4, 6]\) is less than or equal to \(5\) and obviously less than or equal to \(6\).
In the second example you cannot choose any number that only \(2\) elements of the given sequence will be less than or equal to this number because \(3\) elements of the given sequence will be also less than or equal to this number.
Test 2
Input
7 2
3 7 5 1 10 3 20Output
Tutorial
In this problem you can do the following thing: firstly, let's sort our array.
Let \(ans\) will be the answer. Then you have two cases: if \(k = 0\) then \(ans := a_0 - 1\) otherwise \(ans := a_{k - 1}\) (for 0-indexed array).
Then you need to calculate the number of the elements of the array \(a\) that are less than or equal to \(ans\). Let it be \(cnt\). Then if \(ans < 1\) or \(cnt \ne k\) then print "-1" otherwise print \(ans\).
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.