100013 - 快速排序找第k个数

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

输入

第一行包含两个整数n和k(1≤n≤100000,1≤k≤n)
第二行包含n个整数(所有整数均在[1,10^9]范围内),表示整数数列

输出

输出一个整数,表示数列的第k小的数

样例

输入

5 3
2 4 1 5 3

输出

3
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题