题目描述

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}$ ，请注意读入输出效率。