Drilling

Byteman leads a team searching for crude-oil reservoirs. The team has already drilled two boreholes: they found oil at point $A$ and confirmed that there is no oil at point $B$. The reservoir occupies a connected piece of the segment $AB$ with one end exactly at $A$. Byteman now has to determine how far the reservoir reaches along $AB$.

This is not simple, because the drilling speed depends on the location, and the team can drill in only one place at a time. Byteman wants to know in advance how much time he will need, in the worst case, to pinpoint the reservoir's boundary.

Split the segment $AB$ into $n + 1$ equal parts. Place $A$ at coordinate $0$ and $B$ at coordinate $n + 1$; then the candidate points lie at coordinates $1, 2, \ldots, n$. Oil reaches coordinate $0$ (point $A$) but not coordinate $n + 1$ (point $B$), so the boundary is the largest coordinate among $1, 2, \ldots, n$ that still contains oil (it is $0$ if none of them do). Drilling a borehole at point $i$ takes $t_i$ units of time and reveals whether oil is present there.

Design a drilling plan that minimizes the worst-case total time needed to identify the reservoir's boundary, and report that time.

The first line contains one integer $n$ ($1 \le n \le 2000$).

The second line contains $n$ integers $t_1, t_2, \ldots, t_n$ ($1 \le t_i \le 10^6$), separated by single spaces.

Print a single integer: the smallest worst-case total drilling time that guarantees Byteman can identify the reservoir's boundary.

Suppose Byteman drills point $1$ first, spending time $8$. If oil is found there, he still has to learn how far the reservoir reaches to the right, which takes two more boreholes costing $36$ in the worst case, for a total of $44$.

Starting at point $2$ turns out to be better. If point $2$ has no oil, checking point $1$ alone finishes the job. Otherwise, in the worst case he drills points $3$ and $4$ and finishes with total time $42$. Hence $42$ is optimal for this sample.