Initially, Chef had an array A of length N. Chef performs the following operation on A at most once:
Select L and R such that 1 ≤ L ≤ R ≤ N and set A_{i} := A_{i} + 1 for all L ≤ i ≤ R.

Determine the maximum number of inversions Chef can decrease from the array A by applying the operation at most once.
More formally, let the final array obtained after applying the operation at most once be B. You need to determine the maximum value of inv(A) - inv(B) (where inv(X) denotes the number of inversions in array X).

Note: The number of inversions in an array X is the number of pairs (i, j) such that 1 ≤ i < j ≤ N and X_{i} > X_{j}.

------ Input Format ------

• The first line contains a single integer T — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N — the size of the array A.
• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \dots, A_{N}$ denoting the array A.

------ Output Format ------

For each test case, output the maximum value of inv(A) - inv(B) which can be obtained after applying at most one operation.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤N ≤10^{5}$
$1 ≤A_{i} ≤N$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------
3
5
4 2 3 1 5
6
1 2 3 4 5 6
4
2 1 1 1

----- Sample Output 1 ------
2
0
3

----- explanation 1 ------
Test case $1$: The initial array $A$ is $[4, 2, 3, 1, 5]$ which has $5$ inversions. We can perform operation on $L = 3, R = 4$. The resultant array will be $[4, 2, 4, 2, 5]$ which has $3$ inversions. Therefore we reduce the number of inversion by $2$ which is the maximum decrement possible.

Test case $2$: The initial array $A$ is $[1, 2, 3, 4, 5, 6]$ which has $0$ inversions. In this case, we do not need to apply any operation and the final array $B$ will be same as the initial array $A$. Therefore the maximum possible decrement in inversions is $0$.

Test case $3$: The initial array $A$ is $[2, 1, 1, 1]$ which has $3$ inversions. We can perform operation on $L = 2, R = 4$. The resultant array will be $[2, 2, 2, 2]$ which has $0$ inversions. Therefore we reduce the number of inversion by $3$ which is the maximum decrement possible.

见题面

见题面