Problem Description

There is a famous puzzle called "The Tower of Hanoi." The Tower of Hanoi consists of three pegs and N disks of different sizes with a hole in the center. The three pegs are numbered from 1 to 3. The radius of the i-th smallest disk is i centimeters.

Initially, all disks are stacked on peg 1 in descending order of size, forming a "tower." Pegs 2 and 3 are empty. The player can move the top disk of a tower on one peg to the top of a tower on another peg in a single operation. However, a larger disk cannot be placed on top of a smaller disk. The goal of the Tower of Hanoi is to move the tower of height N to either peg 2 or peg 3 with the fewest possible moves.

Takahashi decided to play this puzzle again after finding the toy in the back of his closet. However, it seems someone has played a prank, and all N disks are stacked on peg 1 in random order. Takahashi decided to play a different puzzle starting from this mixed-up state, ignoring the rule that a larger disk cannot be placed on top of a smaller disk, and aiming to move all disks to one peg in descending order of size.

Given the size information of the disks stacked on peg 1, suggest one set of operations to move all disks to one peg (it can be peg 1) in descending order of size. However, since too many operations would make the puzzle unattractive, please move the disks within 225,000 operations.

Input Format

The input is given from the standard input in the following format:

$ N $ $ r_1 $ $ r_2 $ : $ r_N $

• The first line contains the number of disks $N\ (1\ ≦\ N\ ≦\ 10,000)$.
• The next N lines contain the radius $r_i\ (1\ ≦\ r_i\ ≦\ N)$ of the disk initially placed at the i-th position from the bottom on peg 1.
• $r_x\ ≠\ r_y$ if $x\ ≠\ y$.

Output Format

The output format is as follows:

$ M $ $ from_1 $ $ to_1 $ $ from_2 $ $ to_2 $ : $ from_M $ $ to_M $

• The first line should contain the number of operations $ M $.
• The next M lines should contain the peg number $ from_i $ where the disk is moved from and the peg number $ to_i $ where the disk is moved to, separated by a space.
• If there is no disk on peg $ from_i $ during the i-th operation, that operation is invalid. All other operations are valid.
• Note that, unlike the original Tower of Hanoi, placing a larger disk on top of a smaller disk is allowed.
• The solution is considered correct only if $M\ ≦\ 225,000$ and all operations are valid, and finally, all disks are stacked in descending order of size on one peg.

Sample Input and Output

Sample Input #1

5
1
2
3
4
5

Sample Output #1

5
1 2
1 2
1 2
1 2
1 2

Sample Input #2

5
5
3
2
4
1

Sample Output #2

8
1 2
1 2
1 3
1 3
2 1
3 1
3 1
2 1

Notes/Hints

Partial Points

This problem has partial points:

• If you solve the dataset where $1\ ≦\ N\ ≦\ 400$, you get 30 points.
• If you solve the dataset where $1\ ≦\ N\ ≦\ 10,000$, you get an additional 70 points, totaling 100 points.

Sample Explanation 1

Initially, all disks are stacked on peg 1 in reverse order. Moving them one by one to peg 2 will arrange them in descending order from the bottom.

Sample Explanation 2

The peg where all disks are finally stacked can be peg 1.

见题面 Input 部分

见题面 Output 部分