Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2603
Railroad Sort

Time Limit: 2 Seconds      Memory Limit: 32768 KB      Special Judge

Consider the railroad station that has n dead-ends designed in a way shown on the picture. Dead-ends are numbered from right to left, starting from 1.

Let 2n railroad cars get from the right. Each car is marked with some integer number ranging from 1 to 2n, different cars are marked with different numbers.

You can move the cars through the dead-ends using the following two operations. If the car x is the first car on the path to the right of the dead-end i, you may move this car to this dead-end. If the car y is the topmost car in the dead-end j you can move it to the path on the left of the dead-end. Note, that cars cannot be moved to the dead-end from the path to its left and cannot be moved to the path on the right of the dead-end they are in.

Your task is to rearrange the cars so that the numbers on the cars listed from left to right were in the ascending order and all the cars are to the left of all the dead-ends.

One can prove that the required rearranging is always possible.


The input contains multiple test cases. Each test case occupies two lines. The first line of each case contains n - the number of dead-ends (1 <= n <= 13). The second line contains 2n integer numbers - the numbers on the cars, listed from left to right.

A case with n = 0 ends up the input file.


For each case, output the sequence of operations in one line. Each operation is identified with the number of the car moved in this operation. The type of the operation and the dead-end used are clearly determined uniquely.

Sample Input

3 2 1 4
1 2 3 4

Sample Output

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

Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #6
Submit    Status