Given an array *v* of distinct numbers, and a number *k* where *k* is smaller than the size of *v*, find the *k*-th smallest element in the array. A simple solution would be first sorting the array in growing order and than selecting the *k*-th element which can be done in θ(*n* log*n*). However, your program **MUST** run in θ(*n*) on average.

**Difficulty**: Medium.

### Input

There are two lines.

- The first line contains an integer
`k`

- The second line contains an integer
`l`

such that`k`

<=`l`

and`l`

is the length of the array*v*. - The second line consists of
`l`

numbers separated by space which represent the array*v*.

At the end of each line, there are no extra spaces, and there is a `\n`

.

### Output

One line containing 1 integer, which is the *k*-th smallest number in *v*.

### Example

Input:

`3`

`5`

`3 5 2 8 4`

Output:

`4`

### Hint

You can borrow the idea of Quicksort.

### Solution: C++

```
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
using namespace std;
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int v[], int l, int r){
// same as quicksort
int p = v[r-1]; // pivot is the last element
int j=l;
for(int i=l;i<r-1;i++){
if(v[i]<p){
swap(&v[i], &v[j]);
j++;
}
}
swap(&v[j], &v[r-1]);
return j;
}
void find_k_smallest(int v[], int k, int l, int r){
//find the pivot such that v[0...p-1]<v[p]<v[p+1...l]
int p = partition(v, l, r);
//if the pivot is the k-th element, we are done since v[0...k-1]<v[k]<v[k+1...l]
if(p==k-1){
cout<<v[p];
return;
}
//the solution is in v[0...p-1]
if(p>k-1)
find_k_smallest(v, k, l, p);
//the solution is in v[p+1...l]
find_k_smallest(v, k, p+1, r);
}
int main(){
int k;
cin>>k; //index k of the k-th smallest number in the array
int l;
cin>>l; //length of the array
int v[l];
for(int i=0; i<l; i++)
cin>>v[i];
find_k_smallest(v, k, 0, l);
}
```