불만 정렬

정렬 알고리즘이 필요로 하는 교환 횟수의 상한(upper bound)은 $n^2$이며, 이는 쉽게 증명할 수 있다. 아직 올바른 순서가 아닌 두 원소, 즉 $i < j$이면서 $a_i > a_j$인 두 원소를 골라 서로 위치를 바꾸는 연산을 생각하자. 이렇게 순서가 뒤바뀐 쌍을 도치(inversion)라고 하며, 도치의 개수는 최대 $n(n-1)/2$개이다.

현주는 사회에 대한 불만이 많은 아이다. 그래서 정렬을 할 때 원소를 두 개만 고르는 것조차 마음에 들어 하지 않는다. 대신 현주는 $i < j < k$이면서 $a_i > a_j > a_k$인 세 원소를 골라, 그 자리를 $a_k, a_j, a_i$ 순서로 뒤집는 연산을 사용한다.

현주는 이 정렬 방법을 불만 정렬 알고리즘이라고 이름 붙였고, 이제 이 알고리즘의 상한을 구하려고 한다. 즉, 현주가 고를 수 있는 세 원소 조합의 개수를 구하는 프로그램을 작성하라. 다시 말해 $i < j < k$이면서 $a_i > a_j > a_k$를 만족하는 인덱스 삼중항 $(i, j, k)$의 개수를 세면 된다.

첫째 줄에 수열의 길이 $n$이 주어진다. ($1 \le n \le 10^5$)

둘째 줄에 수열의 원소가 공백으로 구분되어 주어진다. 각 원소는 $1$ 이상 $n$ 이하의 정수이다.

첫째 줄에 $i < j < k$이면서 $a_i > a_j > a_k$를 만족하는 세 원소, 즉 인덱스 삼중항 $(i, j, k)$의 개수를 출력한다.