A. Tokitsukaze and Strange Inequality
brute force; data structures; dp
Tokitsukaze 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\).
The 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\).
For each test case, print a single integer — the number of different \([a,b,c,d]\) tuples.
In 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]\).