Triqueue    tri.X

The herd of N (1 <= N <= 1,000) cows is queueing up at the barn for
the evening milking.  Farmer Ran made a new rule that the cows
must form three lines that sort the cows by color:
    * Line 1 is to have black cows 
    * Line 2 is to have brown cows 
    * Line 3 is to have white cows 

Initially the cows are all in line 1 in an order given by the input
file. Slot 1 of the line is the front; slot N is the back. The
integer color number of the cow in slot i is cow_i (1 <= cow_i <=
3). The input data uses 1 to represent black cows, 2 for brown, and
3 for white.

Being of limited intellectual ability, the cows have but one move
to use to get themselves in the proper order: they ask one cow to
amble from the front of one line to the front of another line (thus
pushing the cows in the new line 'back' one slot in the line).

Deduce the optimal scheme for getting the cows into the proper
lines.

In 20% of the test data, the first line will only consist of two different
types of cows.

PROBLEM NAME: tri

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains a single integer the color number of
        the cow in slot i of line 1: cow_i

SAMPLE INPUT:

5
1
2
1
3
3

OUTPUT FORMAT:

* Line 1: A single integer, the minimum number of moves to get the
        cows in order

SAMPLE OUTPUT:

8

OUTPUT DETAILS:

move number
|   moved cow color 
|   | from line     Lines' cows shown from front to back
|   | | to line
|   | | |          Line 1       Line 2       Line 3
|   | | |  init: 1 2 1 3 3    . . . . .    . . . . .
1 | 1 1 3        2 1 3 3 .    . . . . .    1 . . . .
2 | 2 1 2        1 3 3 . .    2 . . . .    1 . . . .
3 | 1 1 2        3 3 . . .    1 2 . . .    1 . . . .
4 | 1 3 2        3 3 . . .    1 1 2 . .    . . . . .
5 | 3 1 3        3 . . . .    1 1 2 . .    3 . . . .
6 | 3 1 3        . . . . .    1 1 2 . .    3 3 . . .
7 | 1 2 1        1 . . . .    1 2 . . .    3 3 . . .
8 | 1 2 1        1 1 . . .    2 . . . .    3 3 . . .