Problem Description

This problem is translated from PA 2022 Round 3 Fotografia.

The graduates of Byte Technology School (Bajtockiej Szkoły Technicznej, BST) gather in the square in front of the school to take a commemorative photo. They stand in one row, with positions numbered from left to right as $1$ to $n$, where $n$ is the number of graduates this year.

The photographer decides to rearrange them so that they are ordered by height in increasing order: the shortest on the far left and the tallest on the far right. Fortunately, no two graduates have the same height.

To avoid confusion, the rearrangement is done in the following way. In one operation, the photographer calls out a sequence of position numbers. The people standing at those positions leave the row in the called order and walk to the middle of the square. Then, the photographer repeats the same list of numbers. The people in the middle return to the called positions in the reverse of the order in which they left.

We want to sort all graduates by increasing height using as few operations as possible. Your task is to plan the rearrangement and tell the photographer, in each operation, which positions to call.

Input Format

The first line contains an integer $n$, the number of graduates.

The next $n$ lines contain an integer sequence $h_1,h_2,\ldots,h_n$, one integer per line, representing the heights of the people standing in the row. All heights are pairwise distinct.

Output Format

The first line should contain an integer $r$, the minimum number of operations needed to sort everyone by increasing height.

The next $2r$ lines describe the operations. For each operation, the first line contains an integer $p_i$, the number of people leaving the row in this operation. The second line contains $p_i$ integers, the position numbers to be called in the order you output. In one operation, the called positions must be distinct.

If there are multiple solutions with the minimum number of operations, output any one of them.

5
1670
2011
1560
1232
1447

1
5
2 1 3 4 5

6
1556
1449
1863
2014
1333
1220

2
5
5 6 1 4 3
4
1 2 3 4

Hint

For $100\%$ of the testdata, it holds that:

$1\le n\le 3 \times 10 ^ 3, 1\le h_i\le 3 \times 10 ^ 3, 1\le p_i\le n$。

Translated by ChatGPT 5