Сложнаяsortingarrays
Число инверсий
Лимит времени 2 с · Память 64 МБПринято: —Решили: 0
Условие
В первой строке дано n, во второй — n целых чисел. Выведите число инверсий: количество пар (i, j) таких, что i < j и a_i > a_j.
Примеры
Пример 1
Ввод
5 2 4 1 3 5
Вывод
3
Пример 2
Ввод
3 1 2 3
Вывод
0
Ограничения
- 1 ≤ n ≤ 10^5
- -10^9 ≤ a_i ≤ 10^9