1. 
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 10810 Ultra-Quicksort
* Link:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=20&page=show_problem&problem=1751
*
* @author Viktoriya Ryabova
*
* @version 1.0, 06/20/2010
*
* Method : Ad-Hoc
* Status : Accapted
* Runtime: 1.104
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
static long counter;

public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
while(true){
int count = Integer.parseInt(r.readLine());

if (count == 0)
break;
counter = 0;
int[] array = new int[count];
for (int i = 0; i < count; i++) {
array[i] = Integer.parseInt(r.readLine());
}
mergeSort(array);
System.out.println(counter);
}
}

public static int[] mergeSort(int array[])
{
if(array.length > 1)
{
int elementsInA1 = array.length/2;
int elementsInA2 = elementsInA1;

if((array.length % 2) == 1)
elementsInA2 += 1;

int arr1[] = new int[elementsInA1];
int arr2[] = new int[elementsInA2];

for(int i = 0; i < elementsInA1; i++)
arr1[i] = array[i];
for(int i = elementsInA1; i < elementsInA1 + elementsInA2; i++)
arr2[i - elementsInA1] = array[i];

arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);

int i = 0, j = 0, k = 0;
while(arr1.length != j && arr2.length != k)
if(arr1[j] < arr2[k])
{
array[i] = arr1[j];
i++;
j++;
}
else
{
array[i] = arr2[k];
i++;
k++;
counter += elementsInA1 - j;
}

while(arr1.length != j)
{
array[i] = arr1[j];
i++;
j++;
}

while(arr2.length != k)
{
array[i] = arr2[k];
i++;
k++;
}
}
return array;
}
}