小W是开染坊的。现在小W的想要把 $n$ 块布染色。这 $n$ 块布每一块都有一个长度 $l_i$。最初这些布都是白色的。

由于一些原因，小W进行染色的方式很奇怪。首先，他将这 $n$ 块布任意排成一排。然后每次选择一种颜色 $c$ 和一个参数 $l$，然后把所有颜色 $c$ 的布块中前 $l$ 块和剩下的分别染成两种不同从未出现过的颜色。

很明显每次染色都需要把所有颜色为 $c$ 的布块重新染色。

小W需要把这 $n$ 块布全部染成互不相同的颜色，他想要最小化他染色的总布块长度。

输入格式

输入自文件$color.in$

第一行一个整数 $n$。

第二行 $n$ 个整数，表示 $l_i$。

输出格式

输出至文件$color.out$

输出一行表示答案。

样例1

input

3
1 4 2

output

10

explanation

按照 1 2 4 的顺序，先把取 $c=\text{白},l=2$，假设之后 1 2 染成了红，4 染成了黄，那么第二次取 $c=\text{红},l=1$。

样例2

input

4
5 6 7 8

output

52

限制与约定

对于 $10\%$ 的数据，$n \le 5$。

对于 $30\%$ 的数据，$n \le 8$。

对于 $60\%$ 的数据，$n \le 10^5$。

对于 $100\%$ 的数据，$1 \le n \le 10^6, 1 \le l_i \le 10^5$。

时间限制：1 s

空间限制：512 MB

提示

本题输入输出量较大，请选择较快的读入方式。

下载

样例数据下载