Задачі
Мега Инверсии
Мега Инверсии
\includegraphics{https://static.e-olymp.com/content/9f/9fd015d565e36146c6caae21d786348ef78aab21.jpg}
Верхнюю оценку $n^2$ в алгоритме сортировки получить легко: достаточно найти два элемента, стоящих в неверном порядке, и поменять их местами. Конрад задумал в алгоритме взять не два, а три стоящих не в правильном порядке элемента. То есть возьмем три элемента $a_i > a_j > a_k$ у которых $i < j < k$ и переставим их в порядке $a_k, a_j, a_i$. Если в исходном алгоритме количество шагов ограничить максимальным числом инверсий $n \cdot (n - 1) / 2$, то Конрад в своей версии алгоритма также хочет ограничить этим значением количество переставляемых троек. Напишите программу, которая подсчитает количество таких троек.
\InputFile
Первая строка содержит длину последовательности $n~(1 \le n \le 10^5)$.
Следующая строка содержит последовательность чисел $a_1, a_2, ..., a_n~(1 \le a_i \le n)$.
\OutputFile
Вывести количество инвертированных троек.
Вхідні дані #1
3 1 2 3
Вихідні дані #1
0
Вхідні дані #2
4 3 3 2 1
Вихідні дані #2
2