## GUPTA MECHANICAL

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

## [Solution] Sorting Array CodeChef Solution | CodeChef Problem Solution 2022

Given an array $A$ of length $N$.

You are allowed to perform the following operation on the array $A$ atmost $20$ times:

• Select a non-empty http://subsequence $S$ of the array $\left[1,2,3,\dots ,N\right]$ and an integer $X$ $\left(0\le X\le {10}^{6}\right)$;
• Change ${A}_{i}$ to ${A}_{i}+X$ for all $i\in S$.

You have to sort the array $A$ in strictly increasing order by performing atmost $20$ operations.

It is guaranteed that we can always sort the array $A$ under given constraints.

### Input Format

• The first line of input contains a single integer $T$, denoting the number of test cases. The description of $T$ test cases follow.

• The first line of each test case contains an integer $N$ - the length of the array.
• The second line of each test case contains $N$ space-separated integers ${A}_{1},{A}_{2},\dots ,{A}_{N}$ representing the initial array $A$.

### Output Format

For each test case print $\left(2\cdot Q+1\right)$ lines. Here $Q$ denotes the number of operations you performed to sort the array $A$. Note that, $Q$ must be less than or equal to $20$. For each test case,

• In the first line, print $Q$, the number of operations you perform.
• Then, print $2\cdot Q$ lines. The $\left(2\cdot i-1{\right)}^{th}$ and $\left(2\cdot i{\right)}^{th}$ of these lines denote the ${i}^{th}$ $\left(1\le i\le Q\right)$ operation.

To describe the ${i}^{th}$ operation, print two space-separated integers ${K}_{i}\left(1\le {K}_{i}\le N\right)$ and ${X}_{i}\left(0\le {X}_{i}\le {10}^{6}\right)$ on $\left(2\cdot i-1{\right)}^{th}$ line and print ${K}_{i}$ space-separated integers describing subsequence ${S}_{i}$ on $\left(2\cdot i{\right)}^{th}$ line.

### Constraints

• $1\le T\le 5\cdot {10}^{4}$
• $2\le N\le {10}^{5}$
• $1\le {A}_{i}\le {10}^{5}$
• Sum of $N$ over all test cases does not exceed ${10}^{5}$.