Interns Mehta and Sharma are waiting for their "build" to complete. Mehta comes up with an interesting game with an array P of integers of size N. She defines the rules of the game as:

1. Pick a number i from the set {1,2,...N-2}.
2. Remove P[i] from the array. You receive P[i-1]*P[i+1] points for doing this removal.
3. Reindex P and loop if possible.

The aim of this game is to reach the highest score possible. Since Sharma loves design and hates maths, please help her reach the highest score possible. She just needs to know the highest score; she will figure out the way to reach it on her own.

Input Format:

The first line contains size of array P.

The next line contains space separated numbers denoting the entries of P.

Output Format:

The highest score possible according to the rules above.

Constraints:

3 <= N <= 50

1 <= Array entries <= 100