消消乐
Description:
那个谁最近迷上了消消乐，他不仅玩儿的废寝忘食，甚至连上课时间都在玩耍。但是毕竟是上课，他不能拿出他50寸的平板电脑，因为那样会挡住后面的同学看黑板。于是他找到了一个一维的消消乐游戏，游戏规则是这样的：
给定一串序列，每次可以选择删除一个数字，并获得与删除数字相邻的数字中，较小的那个数相等的积分。(若删除的是边界数字则不能获得积分。
试问，某次游戏最多能获得多少积分。
Input:
第一行包含一个数字 n ( 1 ≤ n ≤ 5*105) 表述序列有 n 个数
第二行包含 n 个数，ai ( 1 ≤ ai ≤ 106 ) 表示序列第 i 的数的大小
Output:
输出一行包含一个整数表示最多能获得的积分数
Sample Input:
5 3 1 5 2 6
Sample Output:
11
Hint:
删除顺序：1, 2, 5
Submit