题目描述

梦梦需要 n 段木材，第 i 段木材的长度为 $a_i$ 。 ​ 现在梦梦有一根长度为 $\sum_{i=1}^{n} a_i$的木材，他想把他锯成 n 段木材，木材的长度依次为 $a_1,a_2,…,a_n$。 ​ 梦梦可以将一根木材锯成任意长度的两段，锯一根木材的辛苦值为木材锯之前的长度，梦梦想知道满足要求的情况下辛苦值之和最小是多少。 ​

输入格式

一行，给出整数 n 。 第二行给出整数序列 $a_i$ 。

输出格式

输出一行，表示答案。

样例

样例输入

3
8 5 8                                      

样例输出

34                                      

样例解释

​ 先将 21 锯成 13+8 ，再将 13 锯割成 5+8 。 ​

数据范围与提示

​ 对于 30% 的数据， $a_i=1$ 。 ​ 对于 100% 的数据， $1 \leq n \leq 5 \times 10^3,1 \leq a_i \leq 10^5$。 ​