Ультра швидке сортування#1303
У цій задачі вам потрібно проаналізувати певний алгоритм сортування. Алгоритм обробляє послідовність з різних цілих чисел, попарно міняючи місцями два сусідні елементи доти, доки послідовність не буде відсортована у порядку зростання. Наприклад, для вхідної послідовності
9 1 0 5 4
Ultra-QuickSort видає у відповідь
0 1 4 5 9
Ваше завдання — визначити мінімальну кількість необхідних сусідніх перестановок, щоб відсортувати задану послідовність у порядку зростання.
Містить кілька тестових випадків. Перший рядок кожного тестового випадку містить довжину вхідної послідовності (n \leq 500\,000). Кожен з наступних рядків містить одне ціле число a_i (0 \leq a_i \leq 999\,999\,999), -ий елемент послідовності. Останній тестовий випадок містить n = 0 і не повинен оброблятися.
Для кожної вхідної послідовності виведіть один рядок з цілим числом — мінімальною кількістю сусідніх перестановок, необхідних для сортування послідовності.
Приклад 1