CF98D.Help Monks

In a far away kingdom is the famous Lio Shan monastery. Gods constructed three diamond pillars on the monastery's lawn long ago. Gods also placed on one pillar n golden disks of different diameters (in the order of the diameters' decreasing from the bottom to the top). Besides, gods commanded to carry all the disks from the first pillar to the third one according to the following rules:

• you can carry only one disk in one move;
• you cannot put a larger disk on a smaller one.

There was no universal opinion concerning what is to happen after the gods' will is done: some people promised world peace and eternal happiness to everyone, whereas others predicted that the kingdom will face communi… (gee, what am I rambling about?) the Armageddon. However, as everybody knew that it was impossible to solve the problem in less than 2_n_ - 1 moves and the lazy Lio Shan monks never even started to solve it, everyone lives peacefully even though the problem was never solved and nobody was afraid of the Armageddon.

However, the monastery wasn't doing so well lately and the wise prior Ku Sean Sun had to cut some disks at the edges and use the gold for the greater good. Wouldn't you think that the prior is entitled to have an air conditioning system? Besides, staying in the monastery all year is sooo dull… One has to have a go at something new now and then, go skiing, for example… Ku Sean Sun realize how big a mistake he had made only after a while: after he cut the edges, the diameters of some disks got the same; that means that some moves that used to be impossible to make, were at last possible (why, gods never prohibited to put a disk on a disk of the same diameter). Thus, the possible Armageddon can come earlier than was initially planned by gods. Much earlier. So much earlier, in fact, that Ku Sean Sun won't even have time to ski all he wants or relax under the air conditioner.

The wise prior could never let that last thing happen and he asked one very old and very wise witch PikiWedia to help him. May be she can determine the least number of moves needed to solve the gods' problem. However, the witch laid out her cards and found no answer for the prior. Then he asked you to help him.

Can you find the shortest solution of the problem, given the number of disks and their diameters? Keep in mind that it is allowed to place disks of the same diameter one on the other one, however, the order in which the disks are positioned on the third pillar in the end should match the initial order of the disks on the first pillar.

在遥远的王国中，坐落着著名的灵山寺。神明们很久以前就在寺院的草坪上建造了三根钻石柱子。神明们还将 $n$ 个直径各不相同的金盘（自下而上按直径递减排列）放置在其中一根柱子上。此外，神明下令：必须按照如下规则，将所有金盘从第一根柱子搬运至第三根柱子：

• 每次移动只能搬运一个金盘；
• 不允许将较大的金盘置于较小的金盘之上。

至于神明的旨意完成之后究竟会发生什么，人们众说纷纭：有人预言世界将从此和平，人人永享幸福；另一些人则预测王国将面临……（哎呀，我这都在胡扯些什么？）末日浩劫。然而，众所周知，该问题不可能用少于 $2^n - 1$ 步完成，而懒散的灵山寺僧侣们甚至从未着手解决它——因此，尽管问题始终未被解决，人们依然安居乐业，全然不惧末日浩劫。

然而，近来寺院经营状况不佳，睿智的住持顾山孙不得不削去部分金盘的边缘，将所得黄金用于更崇高的事业。难道住持不该拥有一套空调系统吗？况且，整年待在寺院里实在太……无聊了！人总得时不时尝试点新事物，比如去滑雪……顾山孙住持过了许久才意识到自己犯下了多么严重的错误：削边之后，某些金盘的直径变得相同了；这意味着，原先被禁止的一些移动操作如今终于成为可能（毕竟，神明从未禁止将一个金盘放在另一个直径相等的金盘之上）。因此，潜在的末日浩劫可能比神明最初预设的时间提前到来——大大提前。事实上，提前的程度如此之高，以至于顾山孙住持甚至来不及尽情滑雪，或在空调下惬意休憩。

睿智的住持绝不能让最后这种情况发生，于是他求助于一位非常古老、非常睿智的女巫皮基维迪亚。或许她能算出解决神明难题所需的最少移动步数。然而，女巫铺开塔罗牌占卜后，却未能为住持给出答案。于是，他转而向你求助。

给定金盘的数量及其直径，你能找出解决该问题的最短方案吗？请注意：允许将直径相同的金盘叠放在一起；但最终在第三根柱子上金盘的排列顺序，必须与初始时在第一根柱子上的排列顺序完全一致。

The first line contains an integer n — the number of disks (1 ≤ n ≤ 20). The second line contains n integers d__i — the disks' diameters after Ku Sean Sun cut their edges. The diameters are given from the bottom to the top (1 ≤ d__i ≤ 20, besides, d__i ≥ d__i + 1 for any 1 ≤ i < n).

第一行包含一个整数 $n$ —— 圆盘的数量（$1 \leq n \leq 20$）。
第二行包含 $n$ 个整数 $d_i$ —— Ku Sean Sun 切割圆盘边缘后得到的圆盘直径。这些直径按从底到顶的顺序给出（$1 \leq d_i \leq 20$，且对任意 $1 \leq i < n$，均有 $d_i \geq d_{i+1}$）。

Print on the first line number m — the smallest number of moves to solve the gods' problem. Print on the next m lines the description of moves: two space-separated positive integers s__i and t__i that determine the number of the pillar from which the disk is moved and the number of pillar where the disk is moved, correspondingly (1 ≤ s__i, t__i ≤ 3, s__i ≠ t__i).

第一行输出数字 $m$ —— 解决神之问题所需的最少移动次数。
接下来的 $m$ 行，每行输出一次移动的操作描述：两个用空格分隔的正整数 $s_i$ 和 $t_i$，分别表示将圆盘从第 $s_i$ 号柱子移出、移至第 $t_i$ 号柱子（$1 \leq s_i, t_i \leq 3$，且 $s_i \neq t_i$）。

Pay attention to the third test demonstrating that the order of disks should remain the same in the end, even despite the disks' same radius. If this condition was not necessary to fulfill, the gods' task could have been solved within a smaller number of moves (three — simply moving the three disks from the first pillar on the third one).

请注意第三个测试用例，它表明最终圆盘的顺序必须保持不变，即使这些圆盘具有相同的半径。若无需满足此条件，则众神的任务本可在更少的移动次数内完成（仅需三次——直接将三个圆盘从第一根柱子移至第三根柱子）。