Problem Description

Score: $ 600 $ points

There are $ N $ members of the Paken Club standing in a single line from left to right. The height of the $ i $th member from the left is $ A_i $.

Your task is to make the members stand in order of height, that is, for any $i\ (1\leq\ i\leq\ (number of members in the line)-1)$, the condition $ (height of the $ i $left)\ <\$ (i+1) $th member from the left) $ holds, by repeating the following operation zero or more times:

• Let $ M $ be the number of members currently in the line. Choose integers $l,\ r\ (1\leq\ l\leq\ r\leq\ M)$. At the time of choosing, let $ L $ be the height of the $ l $th member from the left and $ R $ be the height of the $ r $th member from the left. Pay the cost $ L+R $ to remove the members from the $ l $th to the $ r $th position from the line.

What is the minimum total cost you need to pay to achieve your task?

An empty line is also considered to be in order of height, and the heights of the members do not change while repeating the operations.

Input Format

The input is given from the standard input in the following format:

\(N\)
\(A_1\) \(A_2\) \(\ldots\) \(A_N\)

Output Format

Output the minimum total cost you need to pay. Do not forget to add a newline at the end of the output.

Sample Input and Output

Sample Input #1

4
3 4 1 2

Sample Output #1

3

Sample Input #2

6
1 2 3 4 5 6

Sample Output #2

0

Sample Input #3

7
1 5 4 7 2 3 6

Sample Output #3

3

Notes/Hints

None

见题面 Input 部分

见题面 Output 部分