hanoig

Let's take 3 rods (A, B and C). Rod A contains n disks of k distinct sizes d₁>d₂>...>d_k.
More specifically, there are m₁ disks of diameter d₁, m₂ disks of diameter d₂, ..., m_k disks of diameter d_k.
Obviously, m₁+m₂+...+m_k=n.
The disks are initially placed on rod A in descending size order, from the base to the top (so at the base we have the m₁ disks of diameter d₁, then the m₂ disks of diameter d₂, ...).
During a move a single disk can be moved from one rod to another, but never will a larger diameter disk be placed over a smaller diameter disk.
The purpose is to move all disks from rod A to rod B, permanently respecting descending size order.
Rod C can be used as a maneuver rod.

Task

Write a program that determines the minimum number of moves that have to be executed to move the n disks from rod A to rod B.

Input Data

Input file hanoig.in contains on the first line a positive integer k, with the meaning in the task description. The second line will contain k positive integers each separated by a space, m₁ m₂ ... m_k.

Output Data

Output file hanoig.out will contain a single line with the minimum number of moves which have to be executed to move the n=m₁+m₂+...+m_k disks from rod A to rod B.

Constraints and Statements

• 0 < k <= 1000
• 0 < m_i <= 1000, for any i=1, 2, ..., k
• The disks are not numbered, therefore disks of the same size are considered identical.
  

Time limit: 0.1 seconds/test

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