题目描述

输入 $n$( 且 $n$ 为奇数)个数字 $a_i$，输出这些数字的第 $k$ 小的数。最小的数是第 $0$ 小。

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

输入格式

第一行2个数字$n,k$。

第二行n个数字$a_i$。

输出格式

输出这些数字的第 $k$ 小的数。

样例

5 1
4 3 2 1 5

2

数据范围

• $1 \le n < 5*10^6$
• $1 \le a_i < {10}^9$
• $k \le n$

来源

洛谷P1923