hanoig

Разглеждаме 3 вертикално поставени колчета (A, B и C), върху които могат да се нанизват дискове. Колчето A съдържа n диска, които са от k различни размера d1>d2>...>dk, т.е. 
има m1 диска с диаметър d1, m2 диска с диаметър d2, ..., mk диска с диаметър dk.
Очевидно m1+m2+...+mk=n.
Първоначално дисковете са нанизани на колчето A по реда на намаляване на размера им от долу нагоре (най-долу има m1 диска с диаметър d1, след това има m2 диска с диаметър d2, ...).
При един ход един диск може да бъде преместен от едно колче на друго, но не е позволено диск с по-голям диаметър да бъде поставен върху диск с по-малък диаметър.
Целта на преместванията е да се поставят всички дискове върху колчето B, като през целия процес на местене да се запазва описаната наредба за размерите.
Колчето C може да се използва като спомагателно - за поставяне и вземане на дискове от там при процеса на преместване.

Задача

Напишете програма, която определя минималния брой ходове, чрез които може да се преместят n-те диска от колчето A на колчето B.

Вход

Входният фаил hanoig.in съдържа на първия си ред положителното цяло число k. Вторият ред на файла съдържа k положителни цели числа, разделени с по един интервал, m1 m2 ... mk.

Изход

Изходният файл hanoig.out трябва да съдържа един ред с търсения минимален брой ходове.

Ограничения и пояснения

Пример
hanoig.in hanoig.out

2
2 3

8

Time limit: 0.1 сек за тест

prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com

Превод на български: Емил Келеведжиев