题目描述

给定长度为 $n$ 的数组 $a$，你需要进行 $n$ 次操作：删去某一元素 $a_i$，并获得 $\min\{a_{i-1}, a_{i+1}\}$ 的分数。若不存在 $a_{i-1}$ 或 $a_{i+1}$，则此次操作不得分。

请你计算至多能得到多少分。

输入格式

第一行一个数 $n$，$1\leq n \leq 5\times 10^5$。

第二行 $n$ 个数，第 $i$ 个数为 $a_i$，$1 \leq a_i \leq 10^6$。

输出格式

一行共一个数，表示最大得分。

5
3 1 5 2 6

11

5
1 2 3 4 5

6

5
1 100 101 100 1

102