Description

You are the TA of the Data Structure course and there are so many students in the class. After the midterm, you are struggling how to find out the students with the  k-th highest score in the class. Since you are the TA of Data Structure you decide to implement an algorithm to solve this problem by yourself OuO.

 

Note: You are only allowed to use vector to complete this problem. To get full score, you need to find out a O(n) solution.

* sorting functions, like sort in <algorithm> or qsort in <stdlib.h>,  are prohibited

(you can import <algorithm> or <stdlib.h> but don't use sort or qsort function)

* data structure like <set> <priority_queue>, <ordered_set> are also prohibited

Input

The first line has two integer numbers, N and K. N indicates there are N students in the class and K indicates you need to find the K highest score in this midterm.

The second line contains N unique unsorted integer scores of the students.

 

Constraint:

0 < K <= N < 10000000

0 <= scores <= 2^31 - 1

Output

Print the k-th highest score in the class.

Note that you need to print ‘\n’ at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss