K-th smallest element in the list

Given n integers and a number k, you are asked to find the k-th smallest element in the list. It’s guaranteed that the array elements are distinct.

Input

The first line of the input contains two integers n and k (1 ≀ k ≀ n ≀ ).
The next line contains n space-separated integers ().

Output

The program should output the value of the k-th smallest element in the given list.

Examples

Input
Output
6 3 10 -2 4 8 3 6
4
7 2 -4 5 8 -3 10 0 7
-3

Explanation

  1. The sorted list would be [-2, 3, 4, 6, 8, 10] β‡’ the 3rd smallest element would be 4
  1. The sorted list would be [-4, -3, 0, 5, 7, 8, 10] β‡’ the 2nd smallest would be -3
Β 
Hint 1
Use random partitioning similar to QuickSort.
Sorting elements is not viable under this time-limit constraint.
Hint 2
You can partition the array similar to QuickSort with a randomly chosen pivot. After which, you can keep only the part of the array that’s needed and ignore the other part.
This process can be repeated until the number of ignored elements BEFORE your current item is equal to k.
Random partitioning will actually have an expected linear time . Do you know why?
Hint 3
Each time we randomly partition the array, the expected size of the resulting array is half the current one. So, if the current array has a size of n, after one partitioning we can throw away half of it - n/2, after two partitioning operations, we can throw away the other half - n/4, and so on. So, this sum becomes .
Yet, the algorithm can have a worst-case performance in case the randomly chosen elements don’t partition the array into an expected n/2 size.
Β 

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue