## GUPTA MECHANICAL

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

## [Solution] Dearrange sorting Solution CodeChef Solution | CodeChef Problem Solution 2022

You are given a permutation $P$ of length $N$. A permutation of length $N$ is an array where every element from $1$ to $N$ occurs exactly once.

You must perform some operations on the array to make it sorted in increasing order. In one operation, you must:

• Select two indices $L$ and $R$ $\left(1\le L
• Completely dearrange the subarray ${P}_{L},{P}_{L+1},\dots {P}_{R}$

A dearrangement of an array $A$ is any permutation $B$ of $A$ for

which ${B}_{i}\ne {A}_{i}$ for all $i$.

For example, consider the array $A=\left[2,1,3,4\right]$. Some examples of dearrangements of $A$ are $\left[1,2,4,3\right]$$\left[3,2,4,1\right]$ and $\left[4,3,2,1\right]$$\left[3,5,2,1\right]$ is not a valid dearrangement since it is not a permutation of $A$$\left[1,2,3,4\right]$ is not a valid dearrangement either since ${B}_{3}={A}_{3}$ and ${B}_{4}={A}_{4}$.

Find the minimum number of operations required to sort the array in increasing order. It is guaranteed that the given permutation can be sorted in atmost $1000$ operations.

### Input Format

• The first line contains a single integer $T$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer $N$ — the size of the permutation $P$.

• The second line of each test case contains $N$ space-separated integers ${P}_{1},{P}_{2},\dots ,{P}_{N}$ denoting the permutation $P$.

### Output Format

• On the first line of each test case output the minimum number of operations $M$. The description of the $M$ operations must follow.
• Each operation must be described in two lines
• On the first line of each operation output two space separated integers $L$ and $R$ $\left(1\le L — the indices of the subarray chosen.
• On the second line output $N$ space separated integers — the permutation $P$ after dearranging the subarray ${P}_{L},{P}_{L+1},\dots {P}_{R}$Note that you have to output the whole permutation $\left\{{P}_{1},{P}_{2},\dots {P}_{N}\right\}$

### Constraints

• $1\le T\le 200$
• $3\le N\le 1000$
• $P$ is a permutation of length $N$
• The sum of $N$ over all test cases does not exceed $1000$
• It is guaranteed that the given permutations can be sorted in atmost $1000$ operations.