题目描述

Smart 和 Sarah 在玩一个游戏，他们有一个队列与一个积分器，最初，队列为空，积分器为 \(0\)。他们总共要进行 \(N\) 步，对于第 \(i\) 步，他们可以选择：

1. 将 \(a_i\) 插入在队尾。 2.如果队列大小不为 \(0\)，将队头弹出，并将分数加上 \(c\)，其中 \(c\) 为队头的数。

最后，如果队列不为空，则重复执行操作 \(2\) 直到队列为空。

Samrt 和 Sarah 都希望分数尽可能小。不过，作为 Sarah 的姐姐，Samrt 先手，他们都会采取最优策略。求最后的得分。

格式

输入格式

第一行输入 \(N\)，下面一行 \(N\) 个数代表数组 \(a_i\)。

输出格式

一个数，代表最终得分。

样例1

样例输入1

6
2 7 4 14 15 7

样例输出1

13

限制

对于 \(10 \%\) 的数据， \(N=1\) ;
对于 \(60 \%\) 的数据， \(1 \leq N \leq 5 \times 10^{3}\) ;
对于 \(100 \%\) 的数据， \(1 \leq N \leq 5 \times 10^{5}, 1 \leq a_{i} \leq 10^{9} \) ，时限 \(1000 \mathrm{~ms}\) ，请注意读入输出效率。