A Strange Tower of Hanoi

There are three rods, and rod 1 holds a stack of $N$ disks. You move one disk at a time. A single move takes the top disk of one rod and puts it on top of another rod.

Seungmin changed the classic Tower of Hanoi puzzle in two places. First, he deleted the rule that a stacked disk must always be smaller than the disk below it, intermediate states included, so while you are moving disks you may put a large disk on a small one. Second, the disks on rod 1 start in an arbitrary order that has nothing to do with their radii.

The goal is to move all $N$ disks to rod 3. In the final state the radii on rod 3 must not increase from the bottom to the top, so no disk ends up resting on a disk with a strictly smaller radius.

Seungmin gave the puzzle to Jinsu and promised him pizza if the number of moves is at most 12345. Help Jinsu get the pizza.

The first line contains the number of disks $N$ ($1 \le N \le 123$).

The second line contains the radii $a_1, a_2, \dots, a_N$ ($1 \le a_i \le N$) of the disks on rod 1, separated by spaces. They are listed starting from the radius of the bottom disk. Several disks may have the same radius.

The puzzle has many valid answers, so print the move sequence produced by the procedure below. While at least one disk remains on rod 1 or rod 2, repeat these four steps.

1. Let $M$ be the largest radius among the disks still on rod 1 and rod 2.
2. For $i = 1, 2$, let $d_i$ be the number of disks lying above the highest disk of radius $M$ on rod $i$. If rod $i$ holds no disk of radius $M$, then $d_i = \infty$.
3. If $d_1 \le d_2$, set $X = 1$ and $Y = 2$. Otherwise set $X = 2$ and $Y = 1$.
4. If the top disk of rod $X$ has radius $M$, move it to rod 3. Otherwise move the top disk of rod $X$ to rod $Y$.

On the first line print the number of moves $K$ that the procedure makes. On each of the next $K$ lines print one move as A B ($1 \le A, B \le 3$), meaning that the top disk of rod $A$ moves to the top of rod $B$. The procedure always finishes within $\frac{N(N+1)}{2} \le 7626$ moves, so $K \le 12345$ always holds.

The picture below shows how the sample is solved.