A convex plot of land is a convex polygon with n corners, given in order around the boundary (either clockwise or counter-clockwise). Corner i carries a positive integer weight v[i].
A triangulation divides the polygon into n-2 triangles using n-3 non-crossing diagonals between corners. The score of a single triangle with corner weights x, y, z is the product x * y * z, and the score of a triangulation is the sum of its triangles' scores.
Report the minimum possible triangulation score over all triangulations.
Input format
Line 1: an integer n, the number of corners.
Line 2: n space-separated positive integers, the corner weights in boundary order.
Output format
A single integer: the minimum triangulation score (0 when n is less than 3, since no triangle exists).
Constraints
- 3 <= n <= 100
- 1 <= each weight <= 100