Очередь в столовой и «хаос»

В школьной столовой стоят в очереди с подносами. Каждый хочет, чтобы впереди были только те, кто пришёл раньше (с меньшим номером талона). Но очередь уже перемешалась.

Назовём пару учеников «конфликтной», если ученик, стоящий левее, имеет *больший* номер талона, чем ученик правее. Чем больше таких пар, тем «хаотичнее» очередь.

Посчитайте количество конфликтных пар.

Формат ввода Первая строка: целое число n — длина очереди. Вторая строка: n целых чисел a1, a2, ..., an — номера талонов слева направо.

Формат вывода Выведите одно целое число — количество конфликтных пар.

Ограничения

• 1 ≤ n ≤ 20000
• 0 ≤ ai ≤ 1 000 000
• Ответ может не помещаться в 32-битный тип (как на олимпиадах), используйте 64-битную арифметику. В Python это не проблема.

Пример Ввод:

5
2 3 9 2 9

Вывод:

2

Ключевое наблюдение: «конфликтная пара» — это ровно инверсия в массиве: индексы i < j, но a[i] > a[j]. Значит, нужно посчитать число инверсий.

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

Почему работает: если слева уже стояло k чисел больше текущего x, то каждый из них образует с x конфликтную пару.

План решения:

• Сожмите значения (coordinate compression): замените каждый a[i] на его ранг в отсортированном списке уникальных значений, чтобы индексы стали 1..m.
• Создайте дерево Фенвика на m позиций (там храним, сколько раз уже встречался каждый ранг).
• Идите по очереди слева направо:
• r = ранг текущего x.
• leq = сколько уже видели значений <= x (это prefix_sum(r)).
• greater = seen - leq — столько слева строго больше x.
• прибавьте greater к ответу и обновите Fenwick: добавить 1 в позицию r.

Мини-сниппет формулы: greater = seen - prefix_sum(r)

Сложность: O(n log n) по времени (и на сжатие, и на n обновлений/запросов), память O(m).

Частая ошибка: забыть про сжатие координат и пытаться строить Fenwick размером до 1_000_000 (или больше, если границы поменяются). Ещё одна: считать >= вместо > — пары с равными талонами НЕ конфликтные.