Tag Archives: Minimal Inversions solution codechef

Minimal Inversions solution codechef

Minimal Inversions solution codechef – Initially, Chef had an array  of length . Chef performs the following operation on  at most once:

  • Select  and  such that 1≤�≤�≤� and set ��:=��+1 for all �≤�≤�.

Minimal Inversions solution codechef

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

Note: The number of inversions in an array  is the number of pairs (�,�) such that 1≤�<�≤� and ��>��.

Input Format

  • The first line contains a single integer  — the number of test cases. Then the test cases follow.
  • The first line of each test case contains an integer  — the size of the array .
  • The second line of each test case contains  space-separated integers �1,�2,…,�� denoting the array .

Minimal Inversions solution codechef

For each test case, output the maximum value of ���(�)−���(�) which can be obtained after applying at most one operation.

Constraints

  • 1≤�≤105
  • 1≤�≤105
  • 1≤��≤�
  • Sum of  over all test cases does not exceed 2⋅105.

Sample 1:

Input

Output

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  is [4,2,3,1,5] which has 5 inversions. We can perform operation on �=3,�=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  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  will be same as the initial array . Therefore the maximum possible decrement in inversions is 0.

Test case 3: The initial array  is [2,1,1,1] which has 3 inversions. We can perform operation on �=2,�=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.