84441 - Payment
时间限制 : 1 秒
内存限制 : 128 MB
小 L 今天一共坐了 n 段地铁，第 i 段原本需要支付 a_i 元。
由于系统延迟，每一段乘车费用不会立即结算，而是按照如下规则统一处理。你可以将连续的几段地铁乘车记录划分为一组进行结算：
- 当一组结算中只有 1 段乘车记录时，不触发任何操作（全额支付）。
- 当一组结算中包含的乘车段数 \ge 2 时，该组乘车费用中最高的一段免费（若有多个最高费用，只免费其中一段）。
请你合理划分结算时间（将整个乘车序列划分为若干个连续的段），使得小 L 最终需要支付的总费用最少。
输入
第一行包含一个整数 n。
第二行包含 n 个整数，第 i 个表示 a_i。
输出
一行一个整数，表示最小的总费用。
样例
输入
5 3 1 4 2 5
输出
6
输入
4 10 10 1 1
输出
11
提示
对于所有的数据，满足：
- 1\le n\le 5\times 10^5；
- 1\le a_i\le 10^9。
来源
MROI-R1