## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Array sorting CodeChef Solution | Codechef Solution 2022

You are given an unsorted permutation $P$ of size $N$. An operation is defined as:

• Swap ${P}_{i}$ and ${P}_{i+K}$ for any $i$ in the range $\left[1,N-K\right]$.

Find the maximum value of $K$, such that, the permutation $P$ can be sorted by applying any finite number of operations.

Solution Click Below:-  👉
👇👇👇👇👇

Note that, a permutation of size $N$ contains all integers from $1$ to $N$ exactly once.

### Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of two lines of input.
• The first line of each test case contains an integer $N$, the size of permutation.
• The next line contains $N$ integers describing the permutation $P$.
• It is guaranteed that the given permutation is not sorted.

### Output Format

For each test case, output on a new line the maximum possible value of $K$.

### Constraints

• $1\le T\le {10}^{5}$
• $2\le N\le {10}^{5}$
• Sum of $N$ over all test cases does not exceed