В этой задаче Вам следует проанализировать работу конкретного алгоритма сортировки. Алгоритм обрабатывает последовательность из n различных целых чисел, меняя местами соседние элементы до тех пор пока все числа не будут находиться в возрастающем порядке. Например для последовательности
9 1 0 5 4
результатом ультра быстрой сортировки будет
0 1 4 5 9
Вам необходимо установить наименьшее количество перестановок соседних элементов, необходимое для расположения всех элементов последовательности в возрастающем порядке.
Состоит из нескольких тестов. Первая строка каждого теста содержит длину входной последовательности n (n ≤ 500,000). Каждая из следующих n строк содержит одно целое число a[i]
(0 ≤ a[i]
≤ 999999999) - i-ый элемент последовательности. Последний тест содержит n = 0 и не обрабатывается.
Для каждой входной последовательности в отдельной строке вывести наименьшее количество перестановок соседних элементов, необходимое для сортировки элементов последовательности.