C. Simple AniPop
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A few years ago, a popular puzzle game named AniPip that particularly appealed to older people like XIRHXQ was hot. And XIRHXQ tries his best to get the highest scores. However, the game is full of randomness and the rules are too complex, so XIRHXQ has a hard time finding an absolutely optimal way to eliminate all the blocks. As a result, XIRHXQ invented a game with simpler rules as a daily pastime, in which he was able to calculate the highest score he could obtain in this game within the time complexity of $$$O(1)$$$.

The rules are as follows.

  • There are a number of objects that need to be eliminated, arranged to form a circle(ring).
  • The player can choose one object per move to eliminate.
  • Each object is given a value, and when you choose to eliminate an object, you get the score whose value equals the product value of the values of that object and the two objects adjacent to it when it is eliminated. (until there exists only one object left)
  • When there is only one object left, the player can eliminate the last object and achieve the score of the last object's value, and then the game is over. The final score is the sum of the scores you get during the game.

Though XIRHXQ can calculate the highest score which the player can achieve immediately, he still gives you the assignment because he wants to play AniPop. When you get the objects and values, you should work out the highest score a player can get, and of course, without the limitation of time complexity of $$$O(1)$$$.

When there are 4 objects and the values are [1,2,3,4] respectively, players can eliminate objects in the order shown below and end up with 84 points!

Input

Two lines.

The first line exists a number $$$n$$$ ($$$1 \le n \le 500$$$) which means there are $$$n$$$ objects.

The second line contains $$$n$$$ values $$$a_{i}(1 \le i \le n , 1 \le a_i \le 100)$$$, they are the values given to the objects.

Output

A number which indicates the highest score the player can get.

Examples
Input
4
1 2 3 4
Output
84
Input
10
45 29 8 3 32 54 88 68 70 83
Output
2304371