题目描述

在一个包含 $n$ 个元素的数组中，找出第 $k$ 个最大的元素。请注意，你需要找的是数组排序后的第 $k$ 个最大的元素，而不是第 $k$ 个不同的元素。 你必须设计并实现时间复杂度为 $O(n)$ 的算法解决此问题。

输入格式

第一行包含两个整数 $n$ 和 $k$，分别表示数组的元素个数和需要找到的第 $k$ 个最大的元素。$\\$ 第二行包含 $n$ 个整数。

输出格式

一个整数，表示答案。

样例

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$，存在负数。