Description

Given $n$ numbers $a_i$, output the $k$-th smallest among them. The smallest number is the $0$-th smallest.

Please try not to use nth_element for this problem, because the main point is to practice divide and conquer algorithms.

Input Format

The first line contains two integers, which are $n$ and $k$.

The second line contains $n$ integers, and the $i$-th number is $a_i$.

Output Format

Output one integer, the $k$-th smallest number.

5 1
4 3 2 1 5

2

Hint

For $100\%$ of the testdata, $1 \le a_i < {10}^9$, $1 \le n < 5 \times 10^6$, and $n$ is odd.

Translated by ChatGPT 5