题目描述

输入 $n$ 个数字 $a_i$，输出这些数字中第 $k$ 小的数。最小的数是第 $0$ 小。

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

输入格式

第一行有两个整数，分别表示 $n$ 和 $k$。

第二行有 $n$ 个整数，第 $i$ 个数表示 $a_i$。

输出格式

一个整数，表示第 $k$ 小的数。

输入样例 #1

5 1
4 3 2 1 5

输出样例 #1

2

输入样例 #2

19 5
77 40 76 21 57 7 28 72 11 41 68 18 77 19 37 93 33 13 73

输出样例 #2

21

输入样例 #3

1 0
1

输出样例 #3

1

数据范围

对于 $100\%$ 的数据，$1\le a_i<{10}^9$，$1 \le n < 5\times 10^6$，$0 \le k < n$。