Problem Description

Xiaoming has $n$ stones, placed in a row in order. He plans to use glue to stick these stones together.

Each stone has its own weight. If two stones are glued together, they will merge into a new stone whose weight is the sum of the two stones' weights.

To make the bonding firm, the amount of glue needed to glue two stones is proportional to the product of their weights. In this problem, physical units are ignored, and the required glue is taken to be numerically equal to the product of the two stones' weights.

In each merge, Xiaoming can only merge two adjacent stones, and the newly merged stone is placed in the original position.

Now, Xiaoming wants to use the least amount of glue to stick all stones together. Please help Xiaoming compute the minimum amount of glue required.

Input Format

The first line of input contains an integer $n$, representing the number of stones initially.

The second line contains $n$ integers $w_1, w_2, \cdots, w_n$, in order, representing the weight of each stone.

Output Format

Output one line containing an integer, representing the minimum amount of glue needed.

3
3 4 5

47

8
1 5 2 6 3 7 4 8

546

Hint

For $20\%$ of the testdata, $1 \le n \le 15$.

For $60\%$ of the testdata, $1 \leq n \leq 100$.

For $80\%$ of the testdata, $1 \leq n \leq 1000$.

For all testdata, $1 \leq n \leq 10^5$, and $1 \leq w_i \leq 1000$.

Lanqiao Cup 2020 First Round Provincial Contest, Group A, Problem I.

Translated by ChatGPT 5