Numbers#1762
Given a sequence of integers a_1, a_2, \ldots, a_n. In one operation, you may remove any element (except the first and last), paying a penalty equal to the product of that element and the sum of its neighbors. Your task is to remove all elements except the first and last with the minimum possible total penalty.
For example, consider the sequence:
1 50 51 50 1
Remove the fourth element: the penalty is 50 \times (1 + 51) = 2600, resulting in:
1 50 51 1
Remove the third element: the penalty is 51 \times (50 + 1) = 2601, resulting in:
1 50 1
Remove the second element: the penalty is 50 \times (1 + 1) = 100.
The total penalty is .
The first line contains a single integer (1 \leq n \leq 100), the number of elements in the sequence.
The second line contains integers a_1, a_2, \ldots, a_n (|a_i| \leq 100).
Print a single integer — the minimum total penalty.
Example 1