e-olymp
Змагання

Дерево Фенвика

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

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

91054

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

01459

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

Вхідні дані

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

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
5
9
1
0
5
4
3
1
2
3
0
Вихідні дані #1
6
0