World is Exploding

Problem Description

Given a sequence A with length n,count how many quadruple (a,b,c,d) satisfies: $a \neq b \neq c \neq d, 1 \leq a < b \leq n, 1 \leq c < d \leq n, A_{a} < A_{b}, A_{c} > A_{d}$.

Input

The input consists of multiple test cases. Each test case begin with an integer n in a single line. The next line contains n integers $A_{1},A_{2}\cdots A_{n}$. $1 \leq n \leq 50000$ $0 \leq A_{i} \leq 1e9$

Output

For each test case,output a line contains an integer.

Sample Input

4
2 4 1 3
4
1 2 3 4

Sample Output

1
0

Author

ZSTU

Source

2016 Multi-University Training Contest 5