Puzzle multiplication#877
In the multiplication puzzle, you play with a number of cards, each containing one positive integer. During a turn, a player removes one card from the series and receives a number of points equal to the product of the number on the removed card and the numbers on the cards lying immediately to its left and right. It is not allowed to remove the first or last card. After the final move, only two cards remain in the series.
The goal of the game is to remove cards in such a manner as to minimize the total number of points.
For example, if the cards contain the numbers , , , , and , the player can take the card with the number , then , then , and obtain points:
If the player removes the cards in reverse order, i.e., , then , then , the number of points would be:
The first line contains the number of cards (3 \leq n \leq 100). The second line contains integers representing the numbers on the cards. The numbers on the cards are integers from to .
Print a single integer — the minimum possible number of points.
Example 1