You are given an array $$$a$$$ containing $$$n$$$ elements. You may remove the elements one by one in any order.
When you remove the $$$i_{th}$$$ element, your score increases by $$$a[i-1].a[i].a[i+1]$$$ points. You can treat elements not within the range of the array to be equal to $$$1$$$.
Determine the maximum total score you can achieve by removing all of the $$$n$$$ elements.
The first line of input contains integer $$$n(1 \le n \le 300)$$$ — the number of elements in $$$a$$$.
The second line of input contains $$$n$$$ integers $$$a_1, a_2... a_n(0 \le a_{i} \le 100)$$$ — the elements of array $$$a$$$.
Output a single integer, the maximum total score that can be achieved.
Input:
4 3 1 5 8
Output:
167
Input:
2 1 5
Output:
10