Given a sequence of numbers a1, a2, ..., an. 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 a1, a2, ..., an, none of the numbers do not exceed 100.

Output

Print a single number - the minimum total cost.