# Permutation Swap solution codeforces

## 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 21052⋅105.

Output

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.

Example

input

Copy
7
3
3 1 2
4
3 4 1 2
7
4 2 6 7 5 3 1
9
1 6 7 4 9 2 3 8 5
6
1 5 3 4 2 6
10
3 10 5 2 9 6 7 8 1 4
11
1 11 6 4 8 3 7 5 9 10 2

output

Copy
1
2
3
4
3
2
3

Note

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 (21=12−1=1 𝑝=[1,3,2]�=[1,3,2]
• Swap 𝑝2�2 and 𝑝3�3 (32=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 (31=23−1=2 𝑝=[1,4,3,2]�=[1,4,3,2]
• Swap 𝑝4�4 and 𝑝2�2 (42=24−2=2 𝑝=[1,2,3,4]�=[1,2,3,4]