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