В библиотеке произошёл полтергейст! Книги на полке перепутались. Библиотекарь хочет узнать, насколько сильно книги перепутаны.
Мера хаоса - это количество ИНВЕРСИЙ. Инверсия - это пара книг (i, j), где i < j, но книга i должна стоять ПОСЛЕ книги j (то есть номер книги i больше номера книги j).
Каждая книга имеет уникальный номер от 1 до N. Идеальный порядок: 1, 2, 3, ..., N.
Помогите библиотекарю подсчитать количество инверсий!
ВХОДНЫЕ ДАННЫЕ:
Первая строка: число N (1 ≤ N ≤ 100000) - количество книг.
Вторая строка: перестановка чисел от 1 до N - текущий порядок книг на полке.
ВЫХОДНЫЕ ДАННЫЕ:
Одно число - количество инверсий.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 2 1
|
3
|
|
2
|
5
2 3 8 6 1
|
5
|