e-olymp
Змагання

Дерево Фенвика

Мега Инверсии

prb6021 Верхнюю оценку n2 в алгоритме сортировки получить легко: достаточно найти два элемента, стоящих в неверном порядке, и поменять их местами. Конрад задумал в алгоритме взять не два, а три стоящих не в правильном порядке элемента. То есть возьмем три элемента ai >aj >ak у которых i < j < k и переставим их в порядке ak, aj, ai. Если в исходном алгоритме количество шагов ограничить максимальным числом инверсий n (n - 1) / 2, то Конрад в своей версии алгоритма также хочет ограничить этим значением количество переставляемых троек. Напишите программу, которая подсчитает количество таких троек.

Входные данные

Первая строка содержит длину последовательности n (1n105). Следующая строка содержит последовательность чисел a1, a2, ..., an (1ain).

Выходные данные

Вывести количество инвертированных троек.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
1 2 3
Вихідні дані #1
0
Вхідні дані #2
4
3 3 2 1
Вихідні дані #2
2
Автор Serikzhan S. Kazi
Джерело 2011 Nordic Collegiate Programming Contest, Problem B