Problem G
Sequence Reduction
We are given a sequence $a_1$, $\dots $, $a_ n$. We can manipulate this sequence using the operation $\text {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$ operations $\text {reduce}(i)$, 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$.
Input
The first line contains $n$ ($1 \le n \le 1\, 000\, 000$), the length of the sequence. The following $n$ lines contain one integer $a_ i$, the elements of the sequence $(0 \le a_ i \le 1\, 000\, 000\, 000)$.
Output
In the first and only line of the output print the minimal cost of reducing the sequence to a single element.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group.
|
Group |
Points |
Constraints |
|
$1$ |
$30$ |
$N \le 500$ |
|
$2$ |
$20$ |
$N \le 20\, 000$ |
|
$3$ |
$50$ |
No additional constraints. |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 2 3 |
5 |