Permutation Swap solution codeforces
You are given an unsorted permutation 𝑝1,𝑝2,…,𝑝𝑛�1,�2,…,��. To sort the permutation, you choose a constant 𝑘� (𝑘≥1�≥1) and do some operations on the permutation. In one operation, you can choose two integers 𝑖�, 𝑗� (1≤𝑗<𝑖≤𝑛1≤�<�≤�) such that 𝑖−𝑗=𝑘�−�=�, then swap 𝑝𝑖�� and 𝑝𝑗��.
What is the maximum value of 𝑘� that you can choose to sort the given permutation?
A permutation is an array consisting of 𝑛� distinct integers from 11 to 𝑛� 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 (𝑛=3�=3 but there is 44 in the array).
An unsorted permutation 𝑝� is a permutation such that there is at least one position 𝑖� that satisfies 𝑝𝑖≠𝑖��≠�.
Inpu
Permutation Swap solution codeforces
Each test contains multiple test cases. The first line contains the number of test cases 𝑡� (1≤𝑡≤1041≤�≤104). The description of the test cases follows.
The first line of each test case contains a single integer 𝑛� (2≤𝑛≤1052≤�≤105) — the length of the permutation 𝑝�.
The second line of each test case contains 𝑛� distinct integers 𝑝1,𝑝2,…,𝑝𝑛�1,�2,…,�� (1≤𝑝𝑖≤𝑛1≤��≤�) — the permutation 𝑝�. It is guaranteed that the given numbers form a permutation of length 𝑛� and the given permutation is unsorted.
It is guaranteed that the sum of 𝑛� over all test cases does not exceed 2⋅1052⋅105.
For each test case, output the maximum value of 𝑘� that you can choose to sort the given permutation.
We can show that an answer always exists.
input
output
1 2 3 4 3 2 3
In the first test case, the maximum value of 𝑘� you can choose is 11. The operations used to sort the permutation are:
- Swap 𝑝2�2 and 𝑝1�1 (2−1=12−1=1) →→ 𝑝=[1,3,2]�=[1,3,2]
- Swap 𝑝2�2 and 𝑝3�3 (3−2=13−2=1) →→ 𝑝=[1,2,3]�=[1,2,3]
In the second test case, the maximum value of 𝑘� you can choose is 22. The operations used to sort the permutation are:
- Swap 𝑝3�3 and 𝑝1�1 (3−1=23−1=2) →→ 𝑝=[1,4,3,2]�=[1,4,3,2]
- Swap 𝑝4�4 and 𝑝2�2 (4−2=24−2=2) →→ 𝑝=[1,2,3,4]�=[1,2,3,4]