题目描述

找出数组中第 k 大的值

Tip：第 k 大表示从最大元素依次找到第 k 大值，而不是不重复数组的第 k 大值，例如数组 {2, 1, 2, 3}，第 3 大值是 2，而不是 1

Format

Input

第一行输入整数 n，表示数组的长度

第二行输入 n 个整数，表示数组的元素

第三行输入整数 k

Output

一个整数，表示元素中第 K 大的值

Samples

10
3 2 3 1 2 4 5 5 5 6
4

5

Limitation

你需要设计一个时间复杂度为 O(n) 的算法

提示：使用快速排序或者堆

• 1 <= k <= n <= 10^5
• -10^4 <= 数组中每一项 <= 10^4