84441 - Payment

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

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

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

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

第一行包含一个整数 n。

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

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

对于所有的数据，满足：

• 1\le n\le 5\times 10^5；
• 1\le a_i\le 10^9。

MROI-R1