1.
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 10810 - Ultra Quick Sort
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=20&problem=1751&mosmsg=Submission+received+with+ID+7504498
*
* @author Felix Dietrich
* @version 1.0, 10/23/2009
*
* Method : Mergesort
* Status : Accepted
* Runtime: 2.432
*/

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


public class Main
{
static long sum;
public static void main(String... s)
{
Scanner sc = new Scanner(System.in);

int n;

while(true)
{
n = sc.nextInt();
if(n == 0)
return;

sum = 0;
List<Integer> l = new ArrayList<Integer>();

for(int i=0; i<n; i++)
{
l.add(sc.nextInt());
}

l = new Main().mergesort(l, 0, l.size()-1);

System.out.println(sum);
//System.out.println(Arrays.toString(l.toArray(new Integer[0])));
}
}

/**
* Uses Mergesort Algorithm to sort the List l
*/
List<Integer> mergesort(List<Integer> l, int left, int right)
{
int mid = ((right+left)/2);

if(right > left)
{
mergesort(l, left, mid);
mergesort(l, mid+1, right);
return merge(l, left, mid+1, right);
}
return l;
}

/**
* Merges the two lists ascending.
* If the first element of a list is smaller than the one on the other list
* this element is added to the new list.
*
* @param list
* @param left
* @param mid
* @param right
* @return the merged list
*/
private List<Integer> merge(List<Integer> list, int left, int mid, int right)
{
List<Integer> l = new ArrayList<Integer>();
int leftsize = mid - 1;
int lSave = left;

while(left <= leftsize && mid <= right)
{
if(list.get(left) <= list.get(mid))
l.add(list.get(left++));
else
{
l.add(list.get(mid++));
sum += leftsize - left + 1;
}
}
while(left <= leftsize)
l.add(list.get(left++));
while(mid <= right)
l.add(list.get(mid++));

for(int i=lSave; i<=right; i++)
list.set(i, l.get(i-lSave));
return list;
}
}