Ханойская башня – одна из известных головоломок. Есть три стержня, на первом из них устанавливаются N дисков разного диаметра в следующем порядке: чем ниже находится диск, тем больше его диаметр. Ваша цель состоит в том, чтобы переместить все диски с первого на второй стержень, используя третий в качестве вспомогательного. По правилам, за один ход можно перенести самый верхний диск с одного стержня на другой. При этом запрещено класть диск большего диаметра на диск меньшего.

Распределение дисков по стержням во время игры можно задать в виде последовательности D, где число D_i равняется номеру стержня, на котором находится диск №i. Например, последовательность D = (3, 3, 1) означает, что первый и второй диски находятся на третьем стержне, а третий диск – на первом стержне.

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

Шаг	Первый стержень	Второй стержень	Третий стержень	последовательность D
0	1, 2, 3	-	-	1, 1, 1
1	2, 3	1	-	2, 1, 1
2	3	1	2	2, 3, 1
3	3	-	1, 2	3, 3, 1
4	-	3	1, 2	3, 3, 2
5	1	3	2	1, 3, 2
6	1	2, 3	-	1, 2, 2
7	-	1, 2, 3	-	2, 2, 2

Ваша цель – определить по последовательности D, задающей некоторую позицию, количество ходов от начала партии до достижения этой позиции при условии выполнения оптимального алгоритма.

Оптимальный алгоритм описывается следующей рекурсивной процедурой.

Например, для перемещения пяти дисков нужно вызвать Hanoi(5, 1, 2, 3).

Первая строка содержит целое число N – количество дисков (1 ≤ N ≤ 31). Следующие N строк содержат целые числа D₁, …, D_N, задающие позицию (1 ≤ D_i ≤ 3).

Выведите количество ходов от начала партии до достижения заданной позиции. Если заданная позиция не может быть достигнута при выполнении оптимального алгоритма, выведите -1.

При выполнении оптимального алгоритма ни одна позиция не повторяется, поэтому ответ всегда будет однозначным.