400364: GYM100151 L Multiswap Sorting

You are employed to implement a new fast sorting algorithm called multiswap sorting. The basic idea is simultaneous execution of multiple parallel swaps. You are given an array containing n integer elements a₁, a₂, ..., a_n. At each step of the algorithm you must select one or more nonintersecting pairs of elements and swap the elements in each of the selected pairs.

For example, you are given the array [5, 4, 3, 2, 1]. At one step you can select two pairs (5, 1) and (4, 2), swap elements in them and get the array 1, 2, 3, 4, 5. Pairs (1, 2) and (2, 3) cannot be selected at one step, because they have the common element 2. So it is possible to sort the array [5, 4, 3, 2, 1] in one step.

Sort the given array in the minimum possible number of steps carrying out selection of pairs at each step optimally. Note that you are not required to minimize the total number of single swaps but the number of steps.

The first line contains an integer n (1 ≤ n ≤ 1000) — the number of elements in the array. In the second line the elements a_i are given. The numbers a_i are integers not exceeding 10⁹ by absolute value.

In the first line output the minimum number of steps k. The next k lines should describe multiswaps in the form «p i₁ j₁ i₂ j₂ ... i_p j_p», where p > 0 is a number of pairs selected at the current step, i_s j_s are the indices of elements in the s-th pair (i_s ≠ j_s, indices of elements in distinct pairs must be distinct). The elements are indexed by integers from 1 to n according to their positions in the array at the current step. The order of pairs and the order of elements in pairs are unimportant. If there are multiple solutions with the minimum number of steps, output any.

3
1 2 3

0

5
5 4 3 2 1

1
2 1 5 2 4

4
3 1 2 2

2
2 1 2 3 4
1 4 2

In the last example, after the first step the array takes the form 1, 3, 2, 2. At the second step 3 is swapped with the last 2. Note that the swap of the 3-rd and the 4-th elements at the first step does not change the array (these elements are equal). However, the answer with this pointless swap, as well as without it, is optimal, because your goal is to minimize the number of steps but not the number of swaps.