== include(page="template/taskheader" task_id="hanoig") ==

Sa consideram $3$ tije (notate $A$, $B$, $C$). Pe tija $A$ se afla $n$ discuri de $k$ dimensiuni distincte $d{~1~}$>$d{~2~}$>...>$d{~k~}$.
Mai exact, exista $m{~1~}$ discuri de diametru $d{~1~}$, $m{~2~}$ discuri de diametru $d{~2~}$, ..., $m{~k~} discuri de diametru $d{~k~}$.

Sa consideram $3$ tije (notate $A$, $B$, $C$). Pe tija $A$ se afla $n$ discuri de $k$ dimensiuni distincte $d{~1~}$> $d{~2~}$>...> $d{~k~}$.
Mai exact, exista $m{~1~}$ discuri de diametru $d{~1~}$, $m{~2~}$ discuri de diametru $d{~2~}$, ..., $m{~k~}$ discuri de diametru $d{~k~}$ .

Evident, $m{~1~}$ + $m{~2~}$ + ... + $m{~k~}$= $n$.
Discurile sunt asezate initial pe tija $A$ in ordinea descrescatoare a dimensiunilor, privind de la baza spre varf (deci la baza sunt cele $m{~1~}$ discuri de diametru $d{~1~}$, apoi urmeaza cele $m{~2~}$ discuri de diametru $d{~2~}$, ...).
La o mutare se poate deplasa un singur disc de pe o tija pe alta, dar niciodata nu va fi plasat un disc de diamentru mai mare peste un disc cu diametru mai mic.

h2. Cerinta

Scrieti un program care sa determine numarul minim de mutari care trebuie sa fie executate pentru a deplasa cele n discuri de pe tija A pe tija B.

Scrieti un program care sa determine numarul minim de mutari care trebuie sa fie executate pentru a deplasa cele $n$ discuri de pe tija A pe tija B.

h2. Date de intrare

Fisierul de intrare $hanoig.in$ contine pe prima linie numarul natural $k$, cu semnificatia din enunt. Pe cea de a doua linie se afla $k$ numere naturale separate prin cate un spatiu $m{~1~}$  $m{~2~}$  ... $m{~k~}$.

Fisierul de intrare $hanoig.in$ contine pe prima linie numarul natural $k$, cu semnificatia din enunt. Pe cea de a doua linie se afla $k$ numere naturale separate prin cate un spatiu $m{~1~}$ $m{~2~}$ ... $m{~k~}$.

h2. Date de iesire

h2. Restrictii

* $0$ < $k$ <= $1000$
* $0$ < $m{~i~}$ <= $1000$, pentru orice $i$= $1$, $2$, ..., $k$

* $0$ < $k$ &le; $1000$
* $0$ < $m{~i~}$ &le; $1000$, pentru orice $i$= $1$, $2$, ..., $k$

* Discurile nu sunt numerotate, prin urmare discurile avand aceeasi dimensiune sunt considerate identice.
h2. Exemplu