[Solution] Tokitsukaze and Strange Inequality solution codeforces

Tokitsukaze and Strange Inequality solution codeforces – Tokitsukaze has a permutation 𝑝p of length 𝑛n. Recall that a permutation 𝑝p of length 𝑛n is a sequence 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn consisting of 𝑛n distinct integers, each of which from 11 to 𝑛n (1𝑝𝑖𝑛1≤pi≤n).

[Solution] Tokitsukaze and Strange Inequality solution codeforces

She wants to know how many different indices tuples [𝑎,𝑏,𝑐,𝑑][a,b,c,d] (1𝑎<𝑏<𝑐<𝑑𝑛1≤a<b<c<d≤n) in this permutation satisfy the following two inequalities:

𝑝𝑎<𝑝𝑐pa<pc and 𝑝𝑏>𝑝𝑑pb>pd.
Note that two tuples [𝑎1,𝑏1,𝑐1,𝑑1][a1,b1,c1,d1] and [𝑎2,𝑏2,𝑐2,𝑑2][a2,b2,c2,d2] are considered to be different if 𝑎1𝑎2a1≠a2 or 𝑏1𝑏2b1≠b2 or 𝑐1𝑐2c1≠c2 or 𝑑1𝑑2d1≠d2.

Input

The first line contains one integer 𝑡t (1𝑡10001≤t≤1000) — the number of test cases. Each test case consists of two lines.

The first line contains a single integer 𝑛n (4𝑛50004≤n≤5000) — the length of permutation 𝑝p.

The second line contains 𝑛n integers 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn (1𝑝𝑖𝑛1≤pi≤n) — the permutation 𝑝p.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 50005000.

[Solution] Tokitsukaze and Strange Inequality solution codeforces

For each test case, print a single integer — the number of different [𝑎,𝑏,𝑐,𝑑][a,b,c,d] tuples.

Example
input

Copy
3
6
5 3 6 1 4 2
4
1 2 3 4
10
5 1 6 2 8 3 4 10 9 7

[Solution] Tokitsukaze and Strange Inequality solution codeforces

output

Copy
3
0
28
Note

In the first test case, there are 33 different [𝑎,𝑏,𝑐,𝑑][a,b,c,d] tuples.

𝑝1=5p1=5𝑝2=3p2=3𝑝3=6p3=6𝑝4=1p4=1, where 𝑝1<𝑝3p1<p3 and 𝑝2>𝑝4p2>p4 satisfies the inequality, so one of [𝑎,𝑏,𝑐,𝑑][a,b,c,d] tuples is [1,2,3,4][1,2,3,4].

Similarly, other two tuples are [1,2,3,6][1,2,3,6][2,3,5,6][2,3,5,6].

For Solution

Click here

Leave a Comment