经典的“汉诺塔”问题是将 $n$ 个大小互不相同的圆盘在 3 根柱子之间移动。在一步操作中，玩家只能将某根柱子最顶端的圆盘移动到另一根柱子的最顶端。圆盘在柱子上必须始终保持自底向上大小递减的顺序（即大盘在下，小盘在上）。最初，这 $n$ 个圆盘都位于 1 号柱子上，目标是将它们全部移动到 3 号柱子上。

传说在一座印度寺庙里，僧侣们自创世以来就一直在解决 64 个圆盘的“汉诺塔”问题。人们相信，一旦这个问题被解决，世界就会毁灭。

然而，这个“宽松汉诺塔”（Relaxed Hanoi）问题并没有那么具有毁灭性。事实上，它相当乐观，因为一旦你正确解决了它，你就会得到通过（Accepted）。在这个变种中，1 号柱子不受顺序规则的限制。换句话说，在任何时刻，1 号柱子上的圆盘都可以以任意顺序排列。

对于给定的“宽松汉诺塔”问题实例，请提供最多 $2 \cdot n^2$ 步移动来解决该问题。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500$) —— 圆盘的数量。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ —— 1 号柱子上从底到顶的圆盘大小（$p_1$ 是最底部的圆盘，$p_n$ 是最顶部的圆盘）。

保证 $p_1, p_2, \dots, p_n$ 构成一个 $1$ 到 $n$ 的排列（换句话说，$1$ 到 $n$ 中的每个数字在 $p_1, p_2, \dots, p_n$ 中恰好出现一次）。

输出格式

第一行应包含一个整数 $k$ ($0 \le k \le 2 \cdot n^2$) —— 移动的步数。

接下来的 $k$ 行，每行应包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le 3$)，表示将最顶端的圆盘从 $a_i$ 号柱子移动到 $b_i$ 号柱子。

最终，所有 $n$ 个圆盘都必须位于 3 号柱子上。

样例

输入样例 1

5
2 1 5 3 4

输出样例 1

9
1 2
1 2
1 3
2 1
2 3
1 3
1 2
1 3
2 3

说明

样例输出仅用了 9 步。对于 $n = 5$，任何不超过 50 步的解法都是可行的。

• 在第 1、2、3 步移动后，状态为 $\langle 2, 1 \rangle \langle 4, 3 \rangle \langle 5 \rangle$。
• 第 4 步移动是合法的，因为 1 号柱子是宽松的。状态为 $\langle 2, 1, 3 \rangle \langle 4 \rangle \langle 5 \rangle$。
• 在第 5、6 步移动后，状态为 $\langle 2, 1 \rangle \langle \rangle \langle 5, 4, 3 \rangle$。
• 最后的第 7、8、9 步移动决定了最终状态为 $\langle \rangle \langle \rangle \langle 5, 4, 3, 2, 1 \rangle$。