int a[1000005];

void QuickSort(int left, int right){
	if(left>=right) return ;
	int i = left;
	int j = right;
	// 设定一个基数
	int key = left;
	while(i<j){
		while(a[key] <= a[j] && i<j) j--;
		while(a[key] >= a[i] && i<j) i++;
		if(i<j) swap(a[i], a[j]);
	}
	swap(a[i], a[key]);
	QuickSort(left, i-1);
	QuickSort(i+1, right);
}