Rainy Day

Lee Hwan, the principal of PS High School, loves the school very much. So every day at lunchtime, Lee Hwan walks around all the buildings of the school. One rainy day, Lee Hwan wanted to walk around the school, but could not, because he hates the rain terribly.

Worried about the rain, Lee Hwan decided to install skybridges between buildings so that he can visit all the buildings of the school without getting rained on. But the students opposed the installation, afraid that they would be caught playing games if Lee Hwan walked around even on a rainy day. If $k$ skybridges connect building $i$ to other buildings, the students playing games in building $i$ have to watch $k$ skybridges for Lee Hwan's approach, so they have $k^2$ units of complaint.

Suppose that at lunchtime, 1 student plays games in building 1, 2 students in building 2, and 3 students in building 3. If skybridges are built as shown below, the students in buildings 2 and 3 each have 1 unit of complaint, and the student in building 1 has 4 units. Thus the students' total complaint is $1 \times 4 + 2 \times 1 + 3\times 1 = 9$. It is impossible to build skybridges so that the complaint is less than 9.

PS High School actually has $N$ buildings, and in building $i$, $a_i$ students play games. Since Lee Hwan gets hurt when the students' complaint is large, you must find the minimum complaint for Lee Hwan's sake.

The first line gives the number of buildings $N$.

The second line gives nonnegative integers $a_1, a_2, \cdots, a_N$, the number of students playing games in each building, separated by spaces.

Print the minimum complaint on the first line.

• $1 \leq N \leq 3 \times 10^5$
• $0 \leq a_i \leq 10^6$ $(1 \le i \le N)$
• All numbers in the input are integers.