Description

Given a convex polygon with $N$ vertices, labeled from $1$ to $N$, each vertex has a positive integer weight. Divide this convex polygon into $N-2$ non-intersecting triangles. Find the minimum possible sum of the products of the vertices' weights for these triangles.

Input Format

The first line of input contains the number of vertices $N$.

The second line lists the weights of vertex $1$ through vertex $N$ in order.

Output Format

Output a single line containing the minimum sum of the products of the vertices' weights for the triangles.

Sample 1

5
121 122 123 245 231

12214884

Constraints and Hints

For $100\%$ of the data, $N\le 50$, and each vertex weight is less than $10^9$.