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 into the accelerator, the i-th particle having mass a_i. The particles spin in the accelerator in a line. 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. 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

The first line contains a single integer n.

The 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