给定一个长度为 $n$ 的整数数列，以及一个整数 $k$，请用快速选择算法求出数列从小到大排序后的第 $k$ 个数。

输入格式

第一行包含两个整数 $n$ 和 $k$。

第二行包含 $n$ 个整数（所有整数均在 $1 \sim 10^9$ 范围内），表示整数数列。

输出格式

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

数据范围

$1 \le n \le 100000$,
$1 \le k \le n$

输入样例：

5 3
2 4 1 5 3

输出样例：

3

已按 OJ 可直接使用的 1.in/1.out ... 生成了 26 组“快速选择求第 k 小”测试数据（覆盖：k=1/k=n、重复值、边界 k 落在重复段、极值、近乎有序、以及 n=100000 压力数据；也包含专门卡朴素 pivot 退化/重复值分区死循环的用例）。

下载测试数据（zip）

下面说明每组 k=1..26 分别在卡哪些常见错误：

1. 样例：基础正确性。
2. n=1,k=1：边界处理（别递归/别越界）。
3. 已升序，k=1：卡不小心把 k 当 0-based（会输出第二小），也卡“直接取第 k 个输入”这类错法。
4. 逆序，k=n：卡 k 端点、以及不排序/错误分区方向。
5. 全相等（50 个），k 在中间：卡分区对重复值处理不当导致死循环/无限递归；也卡返回值不稳定。
6. 小值域大量重复（1..5），k=50：卡重复值、以及分区后 <= / < 边界写错导致 k 落点判断错。
7. 高低交替，k=1：卡最小值查找；也卡某些实现 pivot/交换逻辑错误。
8. 高低交替，k=n：卡最大值查找；以及 k=n 的边界。
9. 含极值与接近极值，k=4：卡比较器用减法溢出（某些语言写 a-b）、以及分区边界错误。
10. 近乎有序，k=90：卡 pivot 选择差导致退化；也卡“没正确缩小区间”的实现。
11. 随机 n=1000，k=777：综合正确性（一般错法会露馅）。
12. 重复块模式，k=1：卡最小值与重复值处理。
13. 重复块模式，k=n：卡最大值与边界。
14. 重复块模式，k=325（恰好落在 25 的最后一个）：卡“k 落在重复段边界”的 off-by-one。
15. 重复块模式，k=326（刚进入 26）：继续卡边界（非常容易写反）。
16. 999 个 100 + 少量 1..10，k=1：卡极端重复 + 少数小值（分区若不稳容易错）。
17. 同上，k=10：卡返回第 10 小（应该是 10），很多错误会被 100 淹没。
18. 同上，k=11：卡从 10 过渡到 100 的边界（k=11 应该是 100）。
19. 同上，k=1000：卡大多数重复值段中的第 k 小（仍是 100），容易写错成 1009/或越界。
20. n=100000 升序，k=50000：强卡朴素 quickselect（pivot=首/尾）退化到 O(n^2) 或递归深度爆。
21. n=100000 逆序，k=50000：同 #20 的另一种退化输入。
22. n=100000 全相等，k=50000：强卡重复值分区死循环/无限递归；也卡性能。
23. n=100000 值域 1..100 大量重复，k=54321：强卡重复值 + k 落在中间；卡三路分区/边界判断。
24. n=100000 全范围随机，k=99999：强卡性能与正确性；也卡 k 接近 n 的边界。
25. n=100000：1..50000 与 1e9 交错，k=50000：k 落在“唯一值段”的末尾（应输出 50000），卡边界判断。
26. 同 #25，k=50001：刚进入重复的 1e9 段（应输出 1e9），专卡 off-by-one。

如果你还想更针对性地卡某个常见错误模板（比如：k 误用 0-based、分区返回的下标区间写错、或 while (i<j) 指针不动），把错误代码思路描述一下，我可以再追加几组“秒杀用例”。