数据太水了 O(n^2)都能过（

#include <iostream>
#include <cstdio>
//#include <algorithm> 
using namespace std;
int a[200005], b[200005];
int *partition(int *left, int *right){
	int *mid = left + (right - left >> 1);
	int *idx;
	if(*left < *mid){
		if(*mid < *right) idx = mid;
		else{
			if(*left < *right) idx = right;
			else idx = left;
		}
	}else{
		if(*mid > *right) idx = mid;
		else{
			if(*left < *right) idx = left;
			else idx = right;
		}
	}
	swap(*left, *idx);
	int pivot = *left;
	while(left != right){
		while(left != right && *right >= pivot) right--;
		*left = *right;
		while(left != right && *left <= pivot) left++;
		*right = *left;
	}
	*left = pivot;
	return left;
}
int nth_element(int *left, int *right, int *tmp){
	int *idx = partition(left, right);
	if(idx == tmp) return *idx;
	if(idx < tmp) return nth_element(idx + 1, right, tmp);
	return nth_element(left, idx - 1, tmp);
}
int read(){
	char c = getchar();
	int x = 0;
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)){
		x = (x << 3) + (x << 1) + c - '0';
		c = getchar();
	}
	return x; 
}
int main(){
	int n = read();
	for(int i = 1; i <= n; i++){
		a[i] = b[i] = read();
	}
	cout << nth_element(a + 1, a + n + 1, a + n + 1) - nth_element(b + 1, b + n + 1, b + 2);

	return 0;
}