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