小 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$。