eolymp
bolt
Try our new interface for solving problems
Problems

Mega Inversions

Mega Inversions

Time limit 1 second
Memory limit 128 MiB

The n^2 upper bound for any sorting algorithm is easy to obtain: just take two elements that are misplaced with respect to each other and swap them. Conrad conceived an algorithm that proceeds by taking not two, but three misplaced elements. That is, take three elements a_i > a_j > a_k with i < j < k and place them in order a_k, a_j, a_i. Now if for the original algorithm the steps are bounded by the maximum number of inversions n \cdot (n - 1) / 2, Conrad is at his wits' end as to the upper bound for such triples in a given sequence. He asks you to write a program that counts the number of such triples.

Input data

The first line is the length of the sequence n~(1 \le n \le 10^5).

The next line contains the integer sequence a_1, a_2, ..., a_n~(1 \le a_i \le n).

Output data

Print the number of inverted triples.

Examples

Input example #1
3
1 2 3
Output example #1
0
Input example #2
4
3 3 2 1
Output example #2
2
Author Serikzhan S. Kazi
Source 2011 Nordic Collegiate Programming Contest, Problem B