// Tang

/* Name: Hong TANG */

void swap(int *x, int *y);

void sort(int* a, int n)
{
	int k, pivot; 
	if (locate_pivot(a, n, &pivot)!= 0) {
		k = partition(a, n, pivot);
		sort(a, k);
		sort(a+k, n-k);
	}
}

locate_pivot(int* a, int n, int* pivot_ptr)  
{
	int b[3], i;
	if (n > 3) {

		if (a[0] < a[n-1]) {
			if (a[n-1] <= a[n/2]) {
				b[0] = a[0];
				b[1] = a[n-1];
				b[2] = a[n/2];
			}
			else if (a[0] <= a[n/2]) {
				b[0] = a[0];
				b[1] = a[n/2];
				b[2] = a[n-1];
			}
			else if (a[n/2] < a[0]) {
				b[0] = a[n/2];
				b[1] = a[0];
				b[2] = a[n-1];
			}
		}

		if (a[0] == a[n-1]) {
			if (a[0] <= a[n/2]) {
				b[0] = a[0];
				b[1] = a[n-1];
				b[2] = a[n/2];
			}
			else {
				b[0] = a[n/2];
				b[1] = a[0];
				b[2] = a[n-1];
			}			
		}
		
		if (a[0] > a[n-1]) {
			if (a[0] <= a[n/2]) {
				b[0] = a[n-1];
				b[1] = a[0];
				b[2] = a[n/2];
			}
			else if (a[n-1] <= a[n/2]) {
				b[0] = a[n-1];
				b[1] = a[n/2];
				b[2] = a[0];
			}
			else if (a[n/2] < a[n-1]) {
				b[0] = a[n/2];
				b[1] = a[n-1];
				b[2] = a[0];
			}
		}

		if (b[0] != b[2]) {
			if (b[0] < b[1]) {
				*pivot_ptr =  b[1];
				return 1;
			}
			else {
				*pivot_ptr =  b[2];
				return 1;
			}

		}
	}

	for (i = 1; i < n; ++i)
		if (a[0] != a[i]) {
			if (a[0] > a[i]) {
				*pivot_ptr =  a[0];
				return 1;
			}
			else {
				*pivot_ptr =  a[i];
				return 1;
			}
		}
	return 0; 
}

partition(int* a, int n, int pivot)
{
	int i = 0, j = n-1;
	while (i <= j) {
		while (a[i] < pivot)
			++i;
		while (a[j] >= pivot)
			--j;
		if (i < j)
			swap(&a[i++], &a[j--]);
	}
	return i;
}

void swap(int* x, int* y)

{
	int temp;
	temp = *x;
	*x = *y;
	*y = temp;
}