В этой задаче Вам следует проанализировать работу конкретного алгоритма сортировки. Алгоритм обрабатывает последовательность из n различных целых чисел, меняя местами соседние элементы до тех пор пока все числа не будут находиться в возрастающем порядке. Например для последовательности

9 1 0 5 4

результатом ультра быстрой сортировки будет

0 1 4 5 9

Вам необходимо установить наименьшее количество перестановок соседних элементов, необходимое для расположения всех элементов последовательности в возрастающем порядке.

Входные данные

Состоит из нескольких тестов. Первая строка каждого теста содержит длину входной последовательности n (n ≤ 500,000). Каждая из следующих n строк содержит одно целое число ai (0 ≤ ai ≤ 999999999) - i-ый элемент последовательности. Последний тест содержит n = 0 и не обрабатывается.

Выходные данные

Для каждой входной последовательности в отдельной строке вывести наименьшее количество перестановок соседних элементов, необходимое для сортировки элементов последовательности.