UVA-10810

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

// The source of this code is http://kasonblog.blogspot.tw/2012/04/10810-ultra-quicksort-uva-online-judge.html
// and its realted information http://program-lover.blogspot.tw/2008/10/mergesort.html
// or http://programming-study-notes.blogspot.tw/2013/12/uva-10810-ultra-quicksort.html
// or http://www.tuicool.com/articles/ANb6Fv

long long ans;
int a1[500100], a2[500100];

void merge_sort(int a, int b) {
	int tmp, mid, t1, t2;

	if (a+1 == b){
		return;
	}

	mid = (a+b)/2;
	
	merge_sort(a,mid);
	merge_sort(mid,b);

	printf("Log> Perform .. %d -> %d\n",a,b);

	t1 = a;
	t2 = mid;

	printf("log> t%d -> t%d\n",t1,t2);

	tmp = a;
	while(t1<mid && t2<b){
		if(a1[t1] < a1[t2]){
			printf("m1  a2[%d] < a1[%d] ( %d <- %d)\n",tmp,t1,a2[tmp],a1[t1]);
			a2[tmp++]= a1[t1++];
		} else {
			printf("m2  a2[%d] < a1[%d] ( %d <- %d)\n",tmp,t2,a2[tmp],a1[t2]);
			a2[tmp++] = a1[t2++];
			ans += mid - t1;
		}
	}

	while(t1<mid){
		printf("31> %d, %d\n",t1,mid);
		a2[tmp++] = a1[t1++];
	}
	while(t2<b){
		printf("32> %d, %d\n",t2,b);
		a2[tmp++] = a1[t2++];
	}

	memcpy(&a1[a], &a2[a], (b-a)*sizeof(int));
}

int main() {
	int n, i;

	while(scanf("%d", &n) != EOF){
		if(n == 0)
			return 0;
		for(i=0; i<n; i++)
			scanf("%d", &a1[i]);
		ans = 0;
		merge_sort(0, n);
		printf("%lld\n", ans);
	}

	return 0;
}