消消乐

Time Limit
1s
Memory Limit
32768KB
Judge Program
Standard
Ratio(Solve/Submit)
23.81%(5/21)
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