eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

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

Первая строка содержит длину последовательности n~(1 \le n \le 10^5).

Следующая строка содержит последовательность чисел a_1, a_2, ..., a_n~(1 \le a_i \le n).

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

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

Пример

Входные данные #1
3
1 2 3
Выходные данные #1
0
Входные данные #2
4
3 3 2 1
Выходные данные #2
2
Автор Serikzhan S. Kazi
Источник 2011 Nordic Collegiate Programming Contest, 1 Октября, Задача B