eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Ультра швидке сортування

Ультра швидке сортування

Ліміт часу 2 секунди
Ліміт використання пам'яті 128 MiB

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

9 1 0 5 4

результатом ультра швидкого сортування буде

0 1 4 5 9

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

Вхідні дані

Складається з декількох тестів. Перший рядок кожного тесту містить довжину вхідної послідовності n (n500,000). Кожен з наступних n рядків містить одне ціле число a[i] (0a[i]999999999) - i-ий елемент послідовності. Останній тест містить n = 0 та не опрацьовується.

Вихідні дані

Для кожної вхідної послідовності в окремому рядку вивести ціле число op - найменшу кількість перестановок сусідніх елементів, необхідних для сортування елементів послідовності.

Приклад

Вхідні дані #1
5
9
1
0
5
4
3
1
2
3
0
Вихідні дані #1
6
0