Maija is yet again playing with nuclear physics. This time she has $n$ particles spinning in an accelerator and she wants to combine them into one massive particle. Particle $i$ has mass $m_i$. In one operation, Maija can pick 2 of the particles that are spinning in the accelerator and collide them. If the masses of the particles were $x$ and $y$, the operation costs $x \times y$ energy and creates a particle with mass $x+y$. Find the most energy efficient way to combine the particles.

Input

The first line contains a single integer $n$: The number of particles.

The second line contains $n$ integers $m_1,\ m_2,\ \dots,\ m_n$: the masses of the particles.

Output

Print one integer: the minimum cost to combine the particles to one.

Constraints

• $2 \leq n \leq 10^5$
• $1 \leq m_i \leq 10^4$

Example 1

Input:

6
3 1 9 9 3 4 

Output:

322

Explanation:
one valid sequence of collisions is:

1 2 3 4 5 6

12 3 4 5 6 -> cost $3 \times 1 = 3$
12 3 5 46 -> cost $9 \times 4 = 36$
12 5 346 -> cost $9 \times 13 = 117$
125 346 -> cost $4 \times 3 = 12$
125346 -> cost $7 \times 22 = 154$

Example 2

Input:

10
123 543 234 639 123 2 432 33 224 988

Output:

4580030