D. Помогите монахам
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Во дворе известного на все Тридевятое царство монастыря Лио Шань давным-давно боги воздвигли три алмазных стержня, возложив на один из них n золотых дисков разного диаметра (в порядке уменьшения диаметра снизу вверх), и повелели перенести все диски с первого стержня на третий по следующим правилам:

  • за один ход разрешается переносить только один диск;
  • нельзя класть больший диск на меньший.
По поводу того, что же произойдет после того, как воля богов будет исполнена, мнения расходились: одни обещали мир во всем мире и вечное счастье всем людям, другие же предрекали скорое пришествие коммуни... (тьфу, о чем это я?) конца света. Однако поскольку все знали, что задачу богов короче, чем за 2n - 1 ходов не решить, а ленивые монахи монастыря Лио Шань к ее решению даже не приступали, все жили мирно и счастливо без всякой задачи, и конца света никто особо не опасался.

Однако дела у монастыря в последнее время шли не очень хорошо, и его мудрому настоятелю Ку Син Сану пришлось обтесать некоторые диски с боков, чтобы использовать золото на благо. В самом деле, нельзя же сидеть настоятелю без кондиционера, да и проводить круглый год в монастыре скучновато — нужно куда-нибудь иногда выбираться, покататься на лыжах, например... Лишь позже Ку Син Сан осознал свою ошибку: после обтесывания диаметры некоторых дисков стали одинаковыми, а значит, некоторые ходы, которые раньше было запрещено осуществлять правилами, теперь стали возможны (в самом деле, класть диск на диск того же диаметра боги не запрещали). Таким образом, возможный конец света мог наступить раньше, чем было задумано богами изначально, и возможно — намного раньше. Настолько раньше, что Ку Син Сан даже не успеет накататься на лыжах и понежиться под кондиционером.

Последнего мудрый настоятель допустить никак не мог и поэтому обратился за помощью к очень старой и очень мудрой колдунье ПикиВедии — может быть, она поможет определить, за какое минимальное количество ходов решается задача богов. Однако, погадав на картах, колдунья не смогла дать настоятелю ответ на его вопрос. Тогда он и обратился за помощью к вам.

Сможете ли вы по заданному количеству дисков и их диаметрам найти кратчайшее решение задачи, при условии, что диски одинакового диаметра разрешено класть один на другой, однако порядок дисков на третьем колышке после всех перемещений должен совпадать с первоначальным порядком дисков на первом колышке?

Входные данные

В первой строке записано целое число n — количество дисков (1 ≤ n ≤ 20). Во второй строке записаны n целых чисел di — диаметры дисков после обтесывания их Ку Син Саном, снизу вверх (1 ≤ di ≤ 20, кроме того, di ≥ di + 1 для любого 1 ≤ i < n).

Выходные данные

В первой строке выведите число m — минимальное количество ходов для решения задачи богов. В следующие m строк выведите описания ходов: два натуральных числа si и ti через пробел, задающие, соответственно, номер колышка, с которого переносится диск, и номер колышка, на который переносится диск (1 ≤ si, ti ≤ 3, si ≠ ti).

Примеры
Входные данные
3
3 2 1
Выходные данные
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3
Входные данные
3
3 1 1
Выходные данные
5
1 2
1 2
1 3
2 3
2 3
Входные данные
3
3 3 3
Выходные данные
5
1 2
1 2
1 3
2 3
2 3
Примечание

Обратите внимание на третий тест, демонстрирующий, что в конце порядок дисков должен остаться прежним, даже несмотря на одинаковый радиус дисков. Без выполнения этого условия задачу богов можно было бы решить за меньшее количество ходов — три (просто переместив три диска с первого колышка на третий).