RT，这个代码会assert failed:

#include<bits/stdc++.h>
using namespace std;
int n,k,a[5000005],b[5000005],ans;
int rd(){return rand()^(rand()<<15);}
void kk(int l,int r)
{
	int mid=a[l+abs(rd())%(r-l+1)],u=l-1,v=r+1,x=0,y=0;
	if(l>r)return; 
	for(int i=l;i<=r;++i)b[i]=-1;
	for(int i=l;i<=r;++i)
	{
		if(a[i]<mid)++u,++x,b[u]=a[i];
		if(a[i]>mid)--v,b[v]=a[i];
	}
	for(int i=l;i<=r;++i)if(b[i]==-1||b[i]==mid)b[i]=mid,++y;
	for(int i=l;i<=r;++i)a[i]=b[i];
	
	if(k<=l+x-1)kk(l,l+x-1);
	else if(k>l+x-1&&k<=l+x+y-1)return;
	else kk(l+x+y,r);
}
int main()
{
	srand(time(0));
	scanf("%d%d",&n,&k),++k;
	for(int i=1;i<=n;++i)scanf("%d",&a[i]),assert(a[i]);
	kk(1,n);
	printf("%d",a[k]);
}
/*
10 3
1 1 1 2 2 2 3 3 4 4

*/