题目描述

输入 $n$（$1 \le n < 10^{6}$ 且 $n$ 为奇数）个数字 $a_i$（$1 \le a_i < {10}^9$），输出这些数字的第 $k$ 小的数。最小的数是第 $1$ 小。

请尽量不要使用 nth_element 来写本题，因为本题的重点在于练习分治算法。

样例输入

第一行为两个正整数 $N$ 和 $K$。

第二行包含 $N$ 个空格隔开的正整数 $a_i$。

样例输出

输出第 $K$ 小的数字

样例

5 3
2 4 1 5 3

3