Background

Luo Siji recently found that the server runs very slowly, so he plans to reconstruct the entire server network to improve efficiency.

Problem Description

Luo Siji has $n$ servers, and each server has a busyness value $v_i$. Luo Siji will connect them together using $n-1$ network links, so each server will have a degree $d_i$, which is the number of connected links. The total running time of this server network is $\sum\limits_{i=1}^n d_i^2 v_i$. Please minimize this value.

Input Format

The first line contains one integer, $n$.
The second line contains $n$ integers, where the $i$-th integer represents $v_i$.

Output Format

The first line contains one integer, the answer.

4
2 3 4 4

28

Hint

Sample Explanation:
Connect three edges $1-2, 1-4, 2-3$. The degrees are $2, 2, 1, 1$, respectively.

Constraints: For $100\%$ of the testdata, $1\leq n\le3\times10^5$ and $1\leq v_i\le10^3$.

Translated by ChatGPT 5