After the Battle of Stalingrad the divisions of the Soviet Army that participated in Operation Ring were re-equipped and sent to other sectors of the front by railway.
When the first train with troops and tanks had been formed, it turned out that the railroaders hadn't thought of the order of the cars. It was decided to use a dead end near the Lazur chemical plant for sorting the cars. Because of its shape, and, perhaps, because of the dozens of German attacks repelled there in November 1942, the dead end was named by German dive-bombers the “Tennis Racket.”
The train is sorted as follows. It is driven tailfirst to the fork and the rear car is uncoupled and brought into the loop. The remaining cars are also uncoupled one by one and brought into the loop along one of the two tracks. They are connected either to the head or to the tail of the newly formed train. When all the cars have been put into the loop, the train is driven out of it headfirst.
The railroaders repeat this operation until the train is sorted. Help them do this task as quickly as possible.
The first line contains the number of cars in the train n (2 ≤ n ≤ 10000). In the next line you are given a permutation of the integers from 1 to n, which describes the initial order of the cars from head to tail. The numbers are separated with a space. After the sorting the cars must be ordered according to their numbers starting from 1.
In the first line output the minimal number of times k the train should be brought into the loop for sorting. In each of the following k lines output n integers describing the order of the cars in the train after the corresponding sorting. If there are several answers, output any of them.
2 5 3 1 6 4
5 1 6 4 3 2
1 2 3 4 6 5
1 2 3 4 5 6
Problem Author: Daniil Ayzenshteyn
Problem Source: Ural Championship 2011