- Time limit: 1.00 s
- Memory limit: 512 MB
Maija has built herself a particle accelerator and is now trying to create the heaviest particle she possibly can. She has put n particles numbered 1,2,\dots,n to the accelerator, the i-th particle having mass a_i. The particles spin in the accelerator in a line formation. Particles i and i+1 are next to each other for all i = 1,2,\dots,n-1. Maija is going to start colliding the particles to create heavier ones. Once particles with masses x and y collide, they create a new particle with mass x+y. Doing this requires x \times y - min(x,y)^2 units of energy. Due to the way Maija built the accelerator, she can only collide adjacent particles and the order of the particles does not change after a collision. Help Maija find the minimum energy cost to combine all the particles.
Input
First line contains a signal integer n.
Second line contains n integers a_1\ a_2\ \dots\ a_n.
Output
Print the minimum energy cost required to combine all the particles into one.
Constraints
- 1 \leq n \leq 500
- 1 \leq a_i \leq 10^6
Example 1
Input:
5 8 10 1 2 4
Output:
97
Explanation:
The optimal sequence of collisions is: 1. Collide particles 3 and 4 -> 34. Cost 1 2. Collide particles 34 and 5 -> 345. Cost 3 3. Collide particles 1 and 2 -> 12. Cost 16 4. Collide particles 12 and 345 -> 12345. Cost 77
Example 2
Input:
1 3
Output:
0
Example 3
Input:
4 1000000 500000 1000000 1
Output:
750000499998