题目描述

给定 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，请找出其中第 $k$ 小的数（最小的数为第 $0$ 小）。

本题鼓励使用分治算法求解。

输入格式

第一行两个正整数 $n$ 和 $k$，以空格隔开。

第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，以空格隔开。

输出格式

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

样例

5 1
4 3 2 1 5

2

提示

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