There are several towers being built simultaneously in the city of Ekaterinburg.
A lot of high quality hardware and materials is needed for the construction,
and most materials are being shipped to the city via railroad.
Railroad delivery isn't always as fast as contractors would like it to be.
Trains spend too much time at the intermediate stations,
being sorted and directed to different regions of the country.
As you know, freight train cars are sorted in the following way:
the train is driven to a twoway switch, where each individual car
can follow either left or right track. After that, the cars are
joined back together.
For example, if the order of the cars in the train is “1 2 3 4 5 6 7”,
they can be split in two parts: “1 3 5” (left track) and “2 4 6 7” (right track),
and then joined: “1 3 5 2 4 6 7”.
Help railroad workers speed up the sorting process. Write
a program to rearrange cars according to the given order
using the minimum number of join operations.
Input
The first line of input contains a single integer N — the number of cars
in the train (1 ≤ N ≤ 10000).
The second line contains N numbers — the initial ordering of the cars.
Each car has an unique number from 1 to N. The cars have to be reordered
so their numbers are increasing, starting from 1.
Output
The first line of ouput shall contain the integer K — minimum number of
times the join must be done.
The following K + 1 lines shall contain N numbers each. Output the initial
ordering of the cars on the first of these lines; each following line
shall contain the ordering achieved with the next join operation.
Samples
input  output 

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

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

Problem Author: Sergey Pupyrev
Problem Source: The XIIth USU Programing Championship, October 6, 2007