Сколько раз нарушили порядок

В школе на линейке класс выстроили в ряд. У каждого ученика на бейдже написано число. Завуч считает, сколько раз в ряду встретилась «неприятная ситуация»: ученик стоит левее, но его число строго больше, чем у ученика правее.

Иными словами, нужно посчитать количество пар индексов (i, j), где 1 ≤ i < j ≤ n и a[i] > a[j].

Формат ввода

Первая строка: целое число n. Вторая строка: n целых чисел a1, a2, …, an.

Формат вывода

Одно целое число — количество таких пар.

Ограничения

• 1 ≤ n ≤ 65000
• −10^9 ≤ ai ≤ 10^9

Пример

Ввод:

5
3 1 2 5 4

Вывод:

3

Ключевое наблюдение: каждая подходящая пара учитывается в момент, когда мы дошли до её правого элемента a[j]. Нужно узнать, сколько элементов слева от него больше a[j].

Проверять все предыдущие элементы напрямую нельзя: получится O(n^2). Вместо этого будем хранить частоты уже просмотренных значений в дереве Фенвика — структуре, которая быстро считает сумму частот на префиксе.

Значения могут быть от -10^9 до 10^9, поэтому нельзя использовать их как индексы. Сделаем сжатие координат: отсортируем все разные значения и заменим каждое его позицией в этом списке, от 1 до m. Порядок чисел при этом сохранится.

• Создайте отсортированный список разных значений и найдите ранг каждого a[i].
• Идите по массиву слева направо. Пусть уже обработано seen чисел, а ранг текущего числа равен r.
• Запрос дерева sum(r) даст количество уже встреченных чисел, которые не больше текущего.
• Тогда больших чисел слева: seen - sum(r). Добавьте это к ответу.
• После подсчёта увеличьте частоту ранга r в дереве Фенвика на 1 и увеличьте seen.

Дубликаты важны: по условию нужно строго >. Поэтому из seen вычитается именно количество значений <= a[i], то есть запрос sum(r), а не sum(r - 1).

Сжатие занимает O(n log n), каждый запрос и обновление дерева — O(log n), всего O(n log n). Ответ может быть порядка n*(n-1)/2; в Python это безопасно, а в языках с фиксированными типами нужен 64-битный целый тип.