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 two-way 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.

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.

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.