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