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≤𝑛≤2⋅1052≤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 2⋅1052⋅105.
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
output
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.