Minimum Glue Cost

You are given n stones arranged in a row. Each stone has a weight. You can merge two adjacent stones at a time. When two stones with weights \(a\) and \(b\) are merged, the resulting stone has a weight of \(a+b\), and the glue cost required for this merge is \(a \times b\). The new stone occupies the position of the two merged stones. Your task is to determine the minimum total glue cost required to merge all the stones into one.

Note: You are only allowed to merge adjacent stones.

Hint: A dynamic programming approach over intervals can be used, where the optimal cost for merging stones in an interval is computed based on possible split positions and the cumulative sums of weights.

inputFormat

The first line contains an integer \(n\) (\(2 \le n \le 500\)), the number of stones.

The second line contains \(n\) positive integers representing the weights of the stones in order.

outputFormat

Output a single number, which is the minimum total glue cost required to merge all the stones into one.

sample

2
3 4

12