Problem Description

题目描述

小 L 今天一共坐了 $n$ 段地铁，第 $i$ 段原本需要支付 $a_i$ 元。

由于系统延迟，每一段乘车费用不会立即结算，而是按照如下规则统一处理。你可以将连续的几段地铁乘车记录划分为一组进行结算：

• 当一组结算中只有 $1$ 段乘车记录时，不触发任何操作（全额支付）。
• 当一组结算中包含的乘车段数 $\ge 2$ 时，该组乘车费用中最高的一段免费（若有多个最高费用，只免费其中一段）。

请你合理划分结算时间（将整个乘车序列划分为若干个连续的段），使得小 L 最终需要支付的总费用最少。

注意：由于本题输入量较大，请关闭同步流或使用快速读入、scanf 等方式完成输入操作。我们在下面提供了一份快读模板。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数，第 $i$ 个表示 $a_i$。

输出格式

一行一个整数，表示最小的总费用。

样例

样例 1

样例 2

提示

【快读模板】

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

【数据范围】

本题采用捆绑测试。

对于所有的数据，满足：

• $1\le n\le 8\times 10^6$；
• $1\le a_i\le 10^9$。

Subtask #0 为样例，占 $0$ 分。

::cute-table{tuack} | 子任务编号 | $n \leq$ | $a_i \leq$ | 分值 | | :-: | :-: | :-: | :-: | | $1$ | $20$ | $10^9$ | $30$ | | $2$ | $2000$ | ^ | $30$ | | $3$ | $2\times 10^5$ | ^ | $30$ | | $4$ | $8\times 10^6$ | ^ | $10$ |

5
3 1 4 2 5

6

4
10 10 1 1

11