← 返回题目列表

Codeforces · 442/C

C. Artem 和阵列

中文机器翻译题面 查看原题

Artem 有一个包含 n 个正整数的数组。阿乔姆决定玩一玩。游戏由n步棋组成。每个动作都是这样进行的。 Artem 选择数组中的某些元素并将其删除。为此,他得到 min(a, b) 点,其中 a 和 b 是与删除的数字相邻的数字。如果该数字的左侧或右侧没有相邻数字,则 Artem 不会获得任何分数。

元素被删除后,数组的两部分粘合在一起,形成 Artem 继续使用的新数组。 Borya 想知道 Artem 在玩这个游戏时最多可以获得多少总分。

输入

第一行包含一个整数 n (1 ≤ n ≤ 5·105) — 数组中的元素数量。下一行包含 n 个整数 ai (1 ≤ ai ≤ 106) — 数组元素的值。

输出

在一行中打印一个整数 - Artem 可以获得的最大点数。

示例

输入 #1

5
3 1 5 2 6

输出 #1

11

输入 #2

5
1 2 3 4 5

输出 #2

6

输入 #3

5
1 100 101 100 1

输出 #3

102