Box Sorting

Interview

Time limit1sMemory limit128 MB

Summary

Sort an array into increasing order using the minimum number of cyclic-rotation commands, following a specified cycle-decomposition construction.

Level: Medium4 of 10
Topics: Array, Simulation, Math
Solved: No attempts yet

Problem

There are N boxes in a row. Each box has a distinct number from 1 to N, and the goal is to arrange the boxes so that the numbers are in increasing order from left to right.

A robot command is a sequence of distinct positions. If the command is p_1, p_2, ..., p_k, then the box currently at position p_i moves to position p_{i+1} for every 1 <= i < k, and the box currently at position p_k moves to position p_1.

Write a program that sorts the boxes using the minimum possible number of commands.

Input

The first line contains the number of boxes N (2 <= N <= 1000).

The next line contains N distinct integers, the numbers written on the boxes in their current order.

Output

Print the number of commands X on the first line.

Then print X lines, one for each robot command in order. Each command line must contain the length of the sequence, then a colon (:), one space, and then the positions in the sequence separated by spaces.

Use this canonical optimal construction. Scan positions from 1 to N. For each unprocessed position, follow the cycle i, A_i, A_{A_i}, ..., where A_i is the box number currently at position i, until the cycle closes. Ignore cycles of length 1. For a cycle of length 2, print the two positions in reverse discovered order. For a cycle of length at least 3, print the positions in discovered order.

Examples3

Example 1
Input
```
3
3 2 1
```
Expected output
```
1
2: 3 1
```
Example 2
Input
```
5
2 3 1 5 4
```
Expected output
```
2
3: 1 2 3
2: 5 4
```
Example 3
Input
```
5
1 2 3 4 5
```
Expected output
```
0
```