18646번 - Quicksort 스페셜 저지다국어

You are given an array of numbers a₁, a₂, . . . , a_n printed on a set of cards that is arranged in a row, and need to sort it in non-decreasing order. The cards are pretty big, so one person can only swap two adjacent cards. However, you have as many people available to do the swapping as you need, as long as they don’t try to swap the same card, so in one step you can do swaps on an arbitrary disjoint set of pairs of adjacent cards.

More formally, in one step you can choose a set of indices i₁, i₂, . . . , i_k such that i₁ + 2 ≤ i₂, i₂ + 2 ≤ i₃, . . . , i_k−1 + 2 ≤ i_k, and swap a_i1 with a_i1+1, a_i2 with a_i2+1, . . . , a_ik with a_ik+1.

Your goal is to sort the given array in non-decreasing order in at most n steps. Note that you don’t need to minimize the number of steps.

The input contains multiple test cases. The first line of the input contains the number t of test cases. Each test case is then described with two lines. The first of those lines contains the size n of the array, 1 ≤ n ≤ 100. The second of those lines contains the elements of the array a₁, a₂, . . . , a_n. The elements of the array are integers between 1 and 10⁹, inclusive.

The sum of values of n in the input does not exceed 1000.

Print the outputs for all test cases in order. For each test case, first print the number m (0 ≤ m ≤ n) of steps that you use to sort the array on a line of its own. On each of the next m lines describe one step with the number k (0 ≤ k ≤ ⌊n/2⌋) of pairs being swapped followed by the indices i₁, i₂, . . . , i_k of the first elements of each pair, printed in increasing order.