问题文

有一个名为「汉诺塔」的著名益智游戏。 汉诺塔由三个柱子和 $N$ 个不同大小的圆盘组成，中间有一个空洞。 柱子被编号为 $1$ 到 $3$。 此外，第 $i$ 个圆盘的半径为 $i$ 厘米。

起初，所有的圆盘都堆叠在柱子 $1$ 上，按照从大到小的顺序形成一个"塔"。 柱子 $2$ 和 $3$ 上没有任何东西。 玩家可以在一次操作中，将某个柱子上的塔顶部的圆盘移动到另一个柱子上，并将其堆叠在目标柱子上的塔顶部。 在此过程中，不能将较大的圆盘放在较小的圆盘上。 汉诺塔的目标是以尽可能少的操作次数，将高度为 $N$ 的塔移动到柱子 $2$ 或柱子 $3$ 上。

Takahashi 决定重新开始解决这个谜题，并从储藏室的深处找出了汉诺塔玩具。 但是，似乎有人捣乱，$N$ 个圆盘以杂乱的顺序堆叠在柱子 $1$ 上。 因此，Takahashi 决定从这种杂乱的状态开始，并忽略"小圆盘上放大圆盘"的规则，将所有的圆盘移动到任意一个柱子上，使得所有圆盘从下到上按照大小的顺序堆叠。

预先知道圆盘半径的信息在柱子 $1$ 上堆叠如下，请给出一种操作，将所有圆盘按照大小的顺序堆叠在任意柱子上（可以是柱子 $1$）。 为了避免操作过多，不能超过 $225,000$ 次操作。

输入

输入以以下格式从标准输入中给出。

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

• 第 $1$ 行包含圆盘的数量 $N (1 \leq N \leq 10,000)$。
• 第 $2$ 行到第 $N+1$ 行分别表示初始时圆盘半径 $r_i (1 \leq r_i \leq N)$。

分部问题

本问题设置了分部问题。

• 如果正确解答了满足 $1 \leq N \leq 400$ 的数据集，则分数为 $30$ 分。
• 如果正确解答了满足 $1 \leq N \leq 10,000$ 的数据集，则额外给予 $70$ 分。总共可以获得 $100$ 分。

输出

输出的格式如下所示。

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

• 第 $1$ 行输出操作的次数 $M$。
• 从第 $2$ 行到第 $M+1$ 行，每行输出第 $i$ 次操作的圆盘所在柱子的编号 $from_i$ 和目标柱子的编号 $to_i$，以空格分隔。
• 如果在第 $i$ 次操作时，柱子 $from_i$ 上没有圆盘，则认为该操作无效。其他操作都被视为有效操作。
• 请注意，与传统的汉诺塔不同，允许将小圆盘放在大圆盘上。
• 当满足 $M \leq 225,000$ 且所有操作均有效，并且最后任意柱子上的所有圆盘按照尺寸从大到小堆叠时，答案将被视为正确。

输入例子1

5
1
2
3
4
5

输出例子1

5
1 2
1 2
1 2
1 2
1 2

最初，所有圆盘逆序堆叠在柱子 $1$ 上。 将它们从上到下依次移动到柱子 $2$ 上，即可按照从大到小的顺序重新排列。

输入例子2

5
5
3
2
4
1

输出例子2

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

最后，所有圆盘也可以堆叠在柱子 $1$ 上。

出处

Code Formula 2014 本战