在一个遥远的王国里,有一座著名的寮山寺。很久以前,众神在寺院的草坪上建造了三根金刚柱。众神还在一根柱子上放置了n个不同直径的金圆盘(按照直径从下到上递减的顺序)。此外,诸神还命令按照以下规则将所有圆盘从第一根柱子搬到第三根柱子:
- 一次只能携带一张圆盘;
- 您不能将较大的磁盘放在较小的磁盘上。
然而,修道院最近生意不太好,明智的院长 Ku Sean Sun 不得不在边缘切掉一些圆盘,并将黄金用于更大的利益。你不认为院长有权拥有空调系统吗?再说了,一整年待在寺院也太无聊了……偶尔也得尝试一下新的东西,比如去滑雪……古肖恩孙过了一段时间才意识到自己犯了多大的错误:他把边缘切掉后,有些圆盘的直径变得一样了;这意味着一些过去不可能的动作终于成为可能(为什么,诸神从来没有禁止将圆盘放在相同直径的圆盘上)。因此,可能的世界末日可能比众神最初计划的更早到来。早得多。事实上,太早了,Ku Sean Sun 甚至没有时间尽情滑雪或在空调下放松。
明智的院长永远不会让最后的事情发生,他请一位非常年长且非常聪明的女巫 PikiWedia 来帮助他。也许她能确定解决诸神的问题所需的最少步数。然而,女巫摆出底牌,却没有找到答案。然后他请求你帮助他。
给定圆盘数量及其直径,你能找到问题的最短解吗?请记住,允许将相同直径的圆盘放置在另一个圆盘上,但是,圆盘最终放置在第三个柱子上的顺序应与圆盘在第一个柱子上的初始顺序相匹配。
输入
第一行包含一个整数 n — 磁盘数量 (1 ≤ n ≤ 20)。第二行包含 n 个整数 di — Ku Sean Sun 切割边缘后圆盘的直径。直径从下到上给出(1 ≤ di ≤ 20,此外,对于任何 1 ≤ i < n,di ≥ di + 1)。
输出
在第一行打印数字 m — 解决诸神的问题的最小步数。在接下来的 m 行上打印移动的描述:两个空格分隔的正整数 si 和 ti,分别确定磁盘移动的柱子编号和磁盘移动的柱子编号,相应地(1 ≤ si,ti ≤ 3,si ≠ ti)。
示例
输入 #1
3 3 2 1
输出 #1
7 1 3 1 2 3 2 1 3 2 1 2 3 1 3
输入 #2
3 3 1 1
输出 #2
5 1 2 1 2 1 3 2 3 2 3
输入 #3
3 3 3 3
输出 #3
5 1 2 1 2 1 3 2 3 2 3
注意
请注意第三个测试,该测试表明,即使圆盘的半径相同,圆盘的顺序最终也应保持不变。如果不需要满足这个条件,众神的任务就可以在更少的移动次数内解决(三步——简单地将三个圆盘从第一根柱子移到第三根柱子上)。