当前没有测试数据。

问题描述

给定长度为 $n$ 的整数数组 a[] 和整数 k，请返回数组中第 k 大的元素。

请注意，你需要找的是数组排序后的第 k 大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

格式

输入

第一行两个整数 $n$ 和 $k$。 第二行为 $n$ 个整数 $a_i$。

输出

数组 a[] 的第 $k$ 大的元素

样例

6 2
3 2 1 5 6 4

5

9 4 
3 2 3 1 2 4 5 5 6

4

提示

• $1 \leq k \leq n \leq 10^5$
• $-10^4 \leq a_i \leq 10^4$