ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Championship 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Train Car Sorting

Time limit: 1.0 second
Memory limit: 64 MB
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.

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

inputoutput
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
To submit the solution for this problem go to the Problem set: 1568. Train Car Sorting