Baltic Olympiad in Informatics: 2007 Day 2, Problem 3

We are given a sequence ~a_1, \dots, a_n~. We can manipulate this sequence using the operation reduce(i), which replaces elements ~a_i~ and ~a_{i+1}~ with a single element ~\max(a_i, a_{i+1})~, resulting in a new shorter sequence. The cost of this operation is ~\max(a_i, a_{i+1})~. After ~n-1~ reduce operations, 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~.

Constraints

~1 \le n \le 10^6~

~0 \le a_i \le 10^9~

Subtask 1 [30%]

~1 \le n \le 500~

Subtask 2 [20%]

~1 \le n \le 2 \times 10^4~

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line of input contains an integer ~n~, the length of the sequence. The following ~n~ lines contain one integer ~a_i~, the elements of the sequence.

Output Specification

Output the minimal cost of reducing the sequence to a single element.

Sample Input

3
1
2
3

Sample Output

5

Explanation for Sample Output

The optimal way to reduce the array to one element has a cost of ~\max(1,2) + \max(2,3)~:

• [1, 2, 3] → [2, 3]
• [2, 3] → [3]