Description

On a playground, there is a row of $N$ piles of stones. Now you need to merge the piles in order into a single pile. Each time, you may only choose two adjacent piles to merge into a new pile, and the number of stones in the new pile is counted as the score of this merge.

Design an algorithm to compute the minimum total score needed to merge the $N$ piles into one pile.

Input Format

The first line contains an integer $N$.

In the next $N$ lines, the $i$-th line contains an integer $a_i$, representing the number of stones in the $i$-th pile.

Output Format

Output the minimum total score to merge all piles into one pile.

4
1
1
1
1

8

Hint

$N \leq 40000, a_i \leq 200$

Please note the range of $N$ (a hint from the uploader).

Translated by ChatGPT 5