typedef struct {
	int len;
	int elem[50240];
} vector;

void printv(char *str, vector v) {
	printf("%s", str);
	int i = 0;
	for (; i < v.len; ++i)
		printf("%d ", v.elem[i]);
	printf("\n");
}

#define MAX(a, b) ((a > b) ? (a) : (b))
#define MIN(a, b) ((a < b) ? (a) : (b))

int partition(vector *v, int p, int r) {
	int x;
	if (p + 3 < r)
		x = MIN(v->elem[p], MAX(v->elem[p+1], v->elem[p+2]));
	else
		x = v->elem[p];
	
	int i = p - 1;
	int j = r + 1;
	while (1) {
		do {
			--j;
		} while (v->elem[j] > x);
		do {
			++i;
		} while (v->elem[i] < x);

		if (i < j) {
			int aux = v->elem[j];
			v->elem[j] = v->elem[i];
			v->elem[i] = aux;
		} else
			return j;			
	}
}

void quicksort_real(vector *v, int p, int r) {
	if (p < r) {
		int q = partition(v, p, r);
		quicksort_real(v, p, q);
		quicksort_real(v, q + 1, r);
	}
}

void quicksort(vector *v) {
	printf("Quicksort...\n");
	quicksort_real(v, 0, v->len - 1);
}