Мега Інверсії

Отримати верхню межу $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)$.

Вихідні дані

Виведіть кількість інвертованих трійок.

Приклади