题目描述

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

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

输入格式

输入共2行

第01行：两个整数n和k，用空格隔开

第02行：n个整数

输出格式

输出共一行，一个整数表示n个数中第k小的数字

样例 #1

样例输入 #1

5 1
4 3 2 1 5

样例输出 #1

2