Minimal Inversions solution codechef – 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\le L\le R\le N$ and set ��:=��+1Ai​:=Ai​+1 for all $L\le i\le R$.

Minimal Inversions solution codechef

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\le i<j\le N$ and ��>��Xi​>Xj​.

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 �1,�2,…,��A1​,A2​,…,AN​ denoting the array $A$.

Minimal Inversions solution codechef

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

Constraints

Sample 1:

3
5
4 2 3 1 5
6
1 2 3 4 5 6
4
2 1 1 1

2
0
3

Minimal Inversions solution codechef

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.