Hanoi#12902

Hanoi

1 second
256 megabytes
Hard

The original problem "Towers of Hanoi" is about moving circular disks of distinct sizes between rods. In one move, the player can move only the top disk from one rod to the top of another. The disks should always be placed one over the other in decreasing order of sizes. Initially, the disks reside on rod and the goal is to have them all reside on rod .

There is a myth of an Indian temple where priests are solving the instance of "Towers of Hanoi" with disks since the beginning of time. It is believed that once this instance is solved, the world will end.

However, this "Relaxed Hanoi" problem is not that apocaliptic. In fact, it is pretty optimistic as once you correctly solve it, you will get a positive verdict. In this variation, rod is not subject to the order rule. In other words, the disks on rod can reside in any order at any point of time.

For an instance of the "Relaxed Hanoi" problem, provide at most 2 \cdot n^2 moves that solve the problem.

Input

The first line of input contains one positive integer (1 \leq n \leq 500) – the number of disks. The second line of input contains integers p_1, p_2, \ldots, p_n – the sizes of the disks on rod from bottom to top (the first is the bottom disk and the -th is the top disk).

It is guaranteed that p_1, p_2, \ldots, p_n form a permutation (in other words, each number from to appears exactly once amongst p_1, p_2, \ldots, p_n).

Output

The first line of output should contain one integer number (0 \leq k \leq 2 \cdot n^2) – the number of moves. Each of the following lines should contain two integer numbers a_i and b_i (1 \leq a_i, b_i \leq 3), describing a move of the topmost disk from rod a_i to rod b_i. At the end, all disks should reside on rod number .

Examples

Example 1

Loading
Loading

Note

The provided output has only moves. Any solution for n=5 with at most moves will work.

  • After moves 2 and , the configuration is \langle 2, 1 \rangle \langle 4, 3 \rangle \langle 5 \rangle.

  • Move is legal as the first stick is relaxed. The configuration is \langle 2, 1, 3 \rangle \langle 4 \rangle \langle 5 \rangle.

  • After moves and , the configuration is \langle 2, 1 \rangle \langle \rangle \langle 5, 4, 3 \rangle.

  • Last moves , and determine the final configuration is \langle \rangle \langle \rangle \langle 5, 4, 3, 2, 1 \rangle.