求第 k 小的数

题目描述

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

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

输入格式

第一行为一个正整数 $N$。

第二行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数。

输出格式

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

5 1
4 3 2 1 5

2

数据范围

$1 \le n < 5000000$ 且 $n$ 为奇数，$1 \le a_i < {10}^9$。