You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

$lh$ 在讲课时发现有的同学居然还不知道什么是树，lh非常气愤，于是决定出一道题来考考大家。

Description

给定一个只包含整数的数组 $A=(A_1,A_2,\dots,A_N)$, 对于一颗有 $N$ 个节点的树 $T$，定义 $f(T)$ 如下：

• 若$d_i$为树$T$中节点$i$的度，则$f(T)=\sum_{i=1}^{N} {d_i^2A_i}$

请你计算出最小的$f(T)$值。

保证最后的答案不超过$2^{63}$

Format

Input

第一行输入一个整数:$N(2{\le}N{\le}2\times{10}^5)$
第二行输入$N$个整数:$A_1{\quad}A_2{\quad}{\dots}{\quad}A_N$$(1{\le}A_i{\le}{10}^9)$

Output

一个整数，代表$f(T)$的最小值

Samples1

4
3 2 5 2

24

Samples2

7
10 5 10 2 10 13 15

128

Limitation

2s, 1024MB for each test case.