NRES 公司最近电梯坏了，员工们不得不通过楼梯上班。每天早上员工们需要从大楼的底部来到大楼的顶部上班。虽然爬楼上班是一件令人火气很大的事情，但是看着前面的人慢吞吞的爬楼是一件更令人愤怒的事情。员工们每天早上按照序号排好队，序号小的在前，同时从底楼出发开始向上爬。由于楼梯很窄，不能超越前面的人，即使你上楼所用的时间比前面一个人要短，你也必须一直跟在他的身后，和他一起到达楼顶。

具体来说，NRES 公司有 $n$ 个员工，第 $i$ 个员工从底楼到顶楼需要 $a_i$ 秒。如果你到达顶楼需要 $x$ 秒，而排在你前一个实际需要的时间是 $y$ 秒，那么你实际需要的时间就是 $\max(x,y)$ 秒。

不幸中的万幸是，NRES 还是有两个楼梯的，员工小 c 负责指挥这段时间的楼梯安排，他可以选择让一部人走第一个楼梯，另外一部分人走另外一个楼梯。两个楼梯上的人互不影响，每个楼梯各自按照序号排序出发。为了减少同事们的怒气，小 c 希望让每个人到达顶楼的时间总和尽量的小，他需要你的帮助。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数表示 $a_i$。

输出格式

一行一个整数表示最小的所有人到达顶楼的时间总和。

样例数据

输入样例一

4
4 3 2 1

输出样例一

12

数据规模与约定

本题采用捆绑测试

对于 20 分的数据，$n \le 20$

对于 40 分的数据，$n\le 1000$

对于另外 10 分的数据，$a_i \le 5$

对于 80 分的数据，$n \le 100000$

对于所有数据，满足 $n\le 500000,1\le a_i \le 10^9$。

时间限制：$5\text{s}$

空间限制：$512\text{MB}$