Frog's Maximum Energy Consumption

You are a little jumping frog who loves to hop around on stones. One day, while playing with your friend F, you encountered a row of stones of various heights. The height of the i-th stone is given by \(h_i\), and the ground is at height \(h_0=0\).

The energy cost to jump from stone \(i\) to stone \(j\) is given by \((h_i-h_j)^2\), and the cost to jump from the ground to stone \(i\) is \((h_i)^2\). You must visit each stone exactly once and may end on any stone. Your goal is to plan a route that maximizes the total energy consumption.

Compute the maximum total energy cost you can achieve by choosing an optimal order of visits.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains a single integer \(n\) (the number of stones). The second line contains \(n\) space-separated integers \(h_1, h_2, \dots, h_n\) representing the stone heights. \(\;\)

outputFormat

Output a single integer representing the maximum total energy cost the frog can consume by following an optimal jumping order.

sample

3
1 3 4

29