2377. Sequence

单点时限: 10.0 sec

内存限制: 256 MB

We are given a sequence a1, …, an. We can manipulate this sequence using the operation reduce(i), which replaces elements ai and ai+1 with a single element max(ai, ai+1), resulting in a new shorter sequence. The cost of this operation is max(ai, ai+1). After n - 1 operations reduce, we obtain a sequence of length 1. Our task is to compute the cost of the optimal reducing scheme, i.e. the sequence of reduce operations with minimal cost leading to a sequence of length 1.

输入格式

The first line contains n (1 ≤n ≤1,000,000), the length of the sequence. The following n lines contain one integer ai, the elements of the sequence (0 ≤ai ≤1,000,000,000).

输出格式

In the first and only line of the output print the minimal cost of reducing the sequence to a single element.

样例

Input
3
1
2
3
Output
5

11 人解决,37 人已尝试。

20 份提交通过,共有 224 份提交。

7.7 EMB 奖励。

创建: 16 年,1 月前.

修改: 7 年,2 月前.

最后提交: 9 月,2 周前.

来源: BOI 2007

题目标签