貌似可以用O(n log n)卡过去

700ms拿下（比正解多了400ms）

#include<bits/stdc++.h>
using namespace std;
const int N=1e7;
int n,a[N];
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-'){
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
    sort(a+1,a+n+1);
	cout<<a[n/2+1];
	return 0;
}