Artem and Array

题意翻译

【题目描述】 给定长度为 $n$ 的数组 $a$ ,你需要进行 $n$ 次操作:删去某一元素 $a_i$ ,并获得 $\min\{a_{i-1}, a_{i+1}\}$ 的分数。若不存在 $a_{i-1}$ 或 $a_{i+1}$,则此次操作不得分。 请你计算至多能得到多少分。 【输入格式】 两行:第一行一个数 $n$ ;第二行 $n$ 个数,第 $i$ 个数为 $a_i$ 【输出格式】 一行共一个数,表示最大得分。 【数据规模】 $1\leq n \leq 5*10^5$ $1 \leq a_i \leq 10^6$

题目描述

Artem has an array of $ n $ positive integers. Artem decided to play with it. The game consists of $ n $ moves. Each move goes like this. Artem chooses some element of the array and removes it. For that, he gets $ min(a,b) $ points, where $ a $ and $ b $ are numbers that were adjacent with the removed number. If the number doesn't have an adjacent number to the left or right, Artem doesn't get any points. After the element is removed, the two parts of the array glue together resulting in the new array that Artem continues playing with. Borya wondered what maximum total number of points Artem can get as he plays this game.

输入输出格式

输入格式


The first line contains a single integer $ n $ $ (1<=n<=5·10^{5}) $ — the number of elements in the array. The next line contains $ n $ integers $ a_{i} $ $ (1<=a_{i}<=10^{6}) $ — the values of the array elements.

输出格式


In a single line print a single integer — the maximum number of points Artem can get.

输入输出样例

输入样例 #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