Задачи
Количество инверсий
Количество инверсий
Напишите программу, которая для заданного массива A = <a1
, a2
, ..., an
> находит количество таких пар (i, j), что i < j и ai
> aj
.
Входные данные
Первая строка содержит количество элементов массива n (1 ≤ n ≤ 50000). Вторая строка содержит n попарно различных элементов массива A - целых неотрицательных чисел, не превосходящих 106
.
Выходные данные
Выведите количество искомых пар.
Входные данные #1
5 6 11 18 28 31
Выходные данные #1
0
Входные данные #2
6 4 7 3 5 2 1
Выходные данные #2
12