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