Sequence II

Long long ago, there is a sequence A with length n. All numbers in this sequence is no smaller than 1 and no bigger than n, and all numbers are different in this sequence.
Please calculate how many quad (a,b,c,d) satisfy:
1. $1\leq a < b < c < d \leq n$
2. $A_{a} < A_{b}$
3. $A_{c} < A_{d}$

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with a line contains an integer n.
The next line follows n integers $A_{1},A_{2}, \ldots, A_{n}$.

[Technical Specification]
1 <= T <= 100
1 <= n <= 50000
1 <= $A_{i}$ <= n

For each case output one line contains a integer,the number of quad.

1
5
1 3 2 4 5

4

BestCoder Round #23