Score : 100 points
There are N slimes lining up in a row. Initially, the i-th slime from the left has a size of a_i.
Taro is trying to combine all the slimes into a larger slime. He will perform the following operation repeatedly until there is only one slime:
Find the minimum possible total cost incurred.
Input is given from Standard Input in the following format:
N a_1 a_2 \ldots a_N
Print the minimum possible total cost incurred.
4 10 20 30 40
190
Taro should do as follows (slimes being combined are shown in bold):
5 10 10 10 10 10
120
Taro should do, for example, as follows:
3 1000000000 1000000000 1000000000
5000000000
The answer may not fit into a 32-bit integer type.
6 7 6 8 6 1 1
68
Taro should do, for example, as follows: