Puzzle multiplication

In multiplication puzzle play with a number of cards, each of which contains one positive integer. During a turn a player removes one card from the series and gets the number of points equal to the product number on the cleaned card and the numbers on the cards, lying immediately to the left and right of it. Are not allowed to remove the first and last card number. After the last course in the series remains the only two cards.

Goal of the game — to remove cards in such a manner as to minimize the total number of points.

For example, if the cards contain numbers $10,1,50,20$ and $5$, the player can take the card with the number $1$, then $20$ and $50$, get points

If he took the cards in reverse order, i.e. $50$, then $20$, then $1$, the number of points would be:

Input

The first line is the number of cards $n(3\le n\le 100)$, the second — $n$ numbers on the cards. The numbers on the cards are integers from $1$ to $100$.

Output

Print a single integer — the minimum possible number of points.

Examples