e-olymp
Competitions

July 12 - ADA Training

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

10 * 1 * 50 + 50 * 20 * 5 + 10 * 50 * 5 = 500 + 5000 + 2500 = 8000

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

1 * 50 * 20 + 1 * 20 * 5 + 10 * 1 * 5 = 1000 + 100 + 50 = 1150

Input

The first line is the number of cards n (3n100), 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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
6
10 1 50 50 20 5
Output example #1
3650