World is Exploding

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}$.

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$

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

4
2 4 1 3
4
1 2 3 4

1
0

ZSTU

2016 Multi-University Training Contest 5