A. Tokitsukaze and Strange Inequalitytime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputTokitsukaze has a permutation p of length n. Recall that a permutation p of length n is a sequence p_1, p_2, \ldots, p_n consisting of n distinct integers, each of which from 1 to n (1 \leq p_i \leq n).She wants to know how many different indices tuples [a,b,c,d] (1 \leq a < b < c < d \leq n) in this permutation satisfy the following two inequalities:  p_a < p_c and p_b > p_d. Note that two tuples [a_1,b_1,c_1,d_1] and [a_2,b_2,c_2,d_2] are considered to be different if a_1 \ne a_2 or b_1 \ne b_2 or c_1 \ne c_2 or d_1 \ne d_2.InputThe first line contains one integer t (1 \leq t \leq 1000) — the number of test cases. Each test case consists of two lines.The first line contains a single integer n (4 \leq n \leq 5000) — the length of permutation p.The second line contains n integers p_1, p_2, \ldots, p_n (1 \leq p_i \leq n) — the permutation p.It is guaranteed that the sum of n over all test cases does not exceed 5000.OutputFor each test case, print a single integer — the number of different [a,b,c,d] tuples.ExampleInput
3
6
5 3 6 1 4 2
4
1 2 3 4
10
5 1 6 2 8 3 4 10 9 7
Output
3
0
28
NoteIn the first test case, there are 3 different [a,b,c,d] tuples.p_1 = 5, p_2 = 3, p_3 = 6, p_4 = 1, where p_1 < p_3 and p_2 > p_4 satisfies the inequality, so one of [a,b,c,d] tuples is [1,2,3,4].Similarly, other two tuples are [1,2,3,6], [2,3,5,6].
3
6
5 3 6 1 4 2
4
1 2 3 4
10
5 1 6 2 8 3 4 10 9 7

3 0 28 
['brute force', 'data structures', 'dp', '*1600']