Lucky Permutation solution codeforces

Lucky Permutation solution codeforces – You are given a permutation 𝑝p of length 𝑛n. In one operation, you can choose two indices 1𝑖<𝑗𝑛1≤i<j≤n and swap 𝑝𝑖pi with 𝑝𝑗pj.

Lucky Permutation solution codeforces

Find the minimum number of operations needed to have exactly one inversion in the permutation.

 A permutation is an array consisting of 𝑛n distinct integers from 11 to 𝑛n in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array), and [1,3,4][1,3,4] is also not a permutation (𝑛=3n=3 but there is 44 in the array).

 The number of inversions of a permutation 𝑝p is the number of pairs of indices (𝑖,𝑗)(i,j) such that 1𝑖<𝑗𝑛1≤i<j≤n and 𝑝𝑖>𝑝𝑗pi>pj.

Lucky Permutation solution codeforces

The first line contains a single integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer 𝑛n (2𝑛21052≤n≤2⋅105).

The second line of each test case contains 𝑛n integers 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn (1𝑝𝑖𝑛1≤pi≤n). It is guaranteed that 𝑝p is a permutation.

Also read: Elemental Decompress solution codeforces

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

Output

For each test case output a single integer — the minimum number of operations needed to have exactly one inversion in the permutation. It can be proven that an answer always exists.

Lucky Permutation solution codeforces

input

Copy
4
2
2 1
2
1 2
4
3 4 1 2
4
2 4 3 1

output

Copy
0
1
3
1

Lucky Permutation solution codeforces

In the first test case, the permutation already satisfies the condition.

In the second test case, you can perform the operation with (𝑖,𝑗)=(1,2)(i,j)=(1,2), after that the permutation will be [2,1][2,1] which has exactly one inversion.

In the third test case, it is not possible to satisfy the condition with less than 33 operations. However, if we perform 33 operations with (𝑖,𝑗)(i,j) being (1,3)(1,3),(2,4)(2,4), and (3,4)(3,4) in that order, the final permutation will be [1,2,4,3][1,2,4,3] which has exactly one inversion.

In the fourth test case, you can perform the operation with (𝑖,𝑗)=(2,4)(i,j)=(2,4), after that the permutation will be [2,1,3,4][2,1,3,4] which has exactly one inversion.

Leave a Reply

Your email address will not be published. Required fields are marked *