Ультра швидке сортування
У цій задачі Вам слід проаналізувати работу конкретного алгоритму сортування. Алгоритм опрацьовує послідовність з 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 та не опрацьовується.
Вихідні дані
Для кожної вхідної послідовності в окремому рядку вивести ціле число op - найменшу кількість перестановок сусідніх елементів, необхідних для сортування елементів послідовності.