A row of n energy cells is arranged left to right; cell i holds a charge value v[i]. You will remove all n cells, one at a time, in an order of your choosing. When you remove a cell, you collect a reward equal to the product of its own charge and the charges of its two current immediate neighbors among the cells still remaining at that moment (the cells that were adjacent to it before any of them were removed may no longer be adjacent once cells between them are gone -- always use whichever cells are currently nearest on each side). If the removed cell has no remaining neighbor on the left (it is the current leftmost remaining cell) or no remaining neighbor on the right, treat the missing neighbor's charge as 1 for that removal. Choose the removal order that maximizes the total reward collected over all n removals, and print that maximum total.
Input format
Line 1: an integer n.
Line 2: n space-separated non-negative integers, the charge values v[0] ... v[n-1].
Output format
A single integer: the maximum total reward achievable over all removal orders.
Constraints
- 1 <= n <= 7
- 0 <= v[i] <= 50