P4393 [BalticOI 2007] Sequence Problem

Given a sequence $a _ 1, \cdots, a _ n$, we perform an operation $\text{reduce}(i)$ that replaces the two elements $a _ i$ and $a _ {i+1}$ with a single element $\max(a _ i,a _ {i+1})$, producing a new sequence shorter than the original. The cost of this operation is $\max(a _ i,a _ {i+1})$. After performing this operation $n-1$ times, we obtain a sequence of length $1$. Our task is to compute the sequence of $\text{reduce}$ operations with the minimum total cost to turn the given sequence into a sequence of length $1$.

The first line contains an integer $n$ ($1 \leq n \leq 10 ^6$), the length of the given sequence. The next $n$ lines each contain an integer $a _ i$ ($0 \leq a _ i \leq 10 ^ 9$), the elements of the sequence.

Output a single line with one integer: the minimum total cost to reduce the sequence to a single element.

- For $30\%$ of the testdata, $n\le 500$. - For $50\%$ of the testdata, $n \le 20000$. - For $100\%$ of the testdata, $1 \le n \le 10^6$, $0 \le a_i \le 10^9$. Translated by ChatGPT 5