539. Multiswap Sorting
Time limit per test: 1
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
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_{1},
a_{2},...,
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.
Input
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
^{9} by absolute value.
Output
In the first line output the minimum number of steps
k. The next
k lines should describe multiswaps in the form "
p i_{1} j_{1} i_{2} j_{2} 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
sth 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.
Example(s)
sample input

sample output

3
1 2 3

0

sample input

sample output

5
5 4 3 2 1

1
2 1 5 2 4

sample input

sample output

4
3 1 2 2

2
2 1 2 3 4
1 4 2

Note
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 3rd and the 4th 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.