Minimizing Server Network Running Time

You are given n servers, each with a busy factor v_i for i = 1, 2, ..., n. You need to connect all the servers by exactly n - 1 network cables so that the resulting network is a tree. Let d_i be the number of connections (degree) of the i-th server in the tree. The total running time of the network is given by:

$$\sum_{i=1}^n d_i^2 v_i$$

Your task is to construct a tree such that the total running time is minimized, and then output this minimum possible value.

Hint: Since a tree with n nodes has exactly n - 1 edges, the sum of all degrees is fixed to 2(n-1). It is optimal to assign as many extra degrees as possible to the server with the smallest busy factor.

inputFormat

The first line contains an integer n (n ≥ 2), the number of servers.

The second line contains n integers v₁, v₂, ..., v_n representing the busy factors of the servers.

outputFormat

Output a single integer representing the minimum total running time of the network.

sample

2
1 2

3