第k大数 给定一个长度为n的整数数列，输出其中第k大的数。

Input 第一行两个数，分别表示n(1≤n≤10^7 )与k(1≤k≤n)。

第二行包含n个整数，表示整个序列。数据保证整数均在int范围内。

Output 仅一行，包含1个整数，表示整个序列中第k大的数。

Example

Input

5 2 3 1 2 4 5

Output

4

这里n的范围在10的7次方 我一直被卡 求助！！！

#include <iostream>
#include <ctime>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 1000010;
int A[N];
int randPartition(int A[], int left, int right)
{
	int p = (round(1.0*rand()/RAND_MAX*(right - left) + left));
	swap(A[p], A[left]);
	int temp = A[left];
	while(left < right)
	{
		while(left < right && A[right] < temp) right--;
		A[left] = A[right];
		while(left < right && A[left] >= temp) left++;
		A[right] = A[left];
	}
	A[left] = temp;
	return left;
}
int randSelect(int A[], int left, int right, int k)
{
	if(left == right) return A[left];
	int p = randPartition(A, left, right);
	int m = p - left + 1;
	if(k==m) return A[p];
	if(k < m){
		return randSelect(A, left, p - 1, k);
	}
	else
	{
		return randSelect(A, p + 1, right, k - m);
	}
}

int main()
{
	srand((unsigned)time(NULL));
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <=  n; i++) cin >> A[i];
	
	int m = randSelect(A, 1, n, k);
	
	cout << m << endl;
	return 0; 
}