Numbers
Given a sequence of numbers a[1], a[2], ..., a[n]. One operation is allowed to remove any (except the extreme) number, paying a fine equal to the product of that number, the amount of its neighbors. You want to delete all numbers, except the extreme, with a minimum total cost.
For example, consider the initial sequence:
1 50 51 50 1
delete the fourth number, the fine 50 * (1 + 51) = 2600, we get
1 50 51 1
remove the third number, a fine 51 * (50 + 1) = 2601, we get
1 50 1
remove the second number, a fine 50 * (1 + 1) = 100.
Total fine 5301.
Input
The first line contains one integer n (1 ≤ n ≤ 100) - the amount of numbers in sequence. The second line contains n integers a[1], a[2], ..., a[n], none of the numbers do not exceed 100.
Output
Print a single number - the minimum total cost.