Эта задача представляет собой модификацию известной задачи о ханойских башнях. Имеется три стержня и 2n дисков n разных размеров, по два диска каждого размера. Диски пронумерованы целыми числами от 1 до 2n в порядке неубывания размеров. Таким образом, диски одного размера имеют номера 2i - 1 и 2i. Диски можно нанизывать на стержни. За один ход разрешается перемещать только один диск сверху любого стержня наверх любого другого стержня, причем нельзя класть больший диск на меньший.
Изначально все диски расположены на первом стержне в порядке убывания номеров (считая снизу вверх). В конце они все должны оказаться на втором стержне в определенном заданном порядке. Ваша задача состоит в том, чтобы найти наименьшее количество ходов для получения конечного расположения дисков из начального. Обратите внимание, что диски одинаковых размеров с разными номерами считаются различными.
Первая строка содержит одно целое число n (1 ≤ n ≤ 2000). Вторая строка описывает конечное расположение дисков на втором стержне. Она содержит 2n номеров в порядке снизу вверх. Гарантируется, что каждый из 2n дисков встречается в заданной последовательности ровно один раз. Конечное расположение дисков корректно, т.е. никакой диск большего размера не лежит на меньшем диске.
Выведите требуемое наименьшее количество ходов.
1
2 1
3
| Название |
|---|


