SP4305 AE3A - Drilling

Byteman has asked you for help. He has divided the segment connecting points A and B into $n+1$ segments of equal length. If we assume that point A has coordinate $0$, and point B coordinate $n + 1$, then there are $n$ points with coordinates $1\dots n$ between them. It is enough to find the farthest from A of these points in which some crude oil occurs. Byteman has informed you about the amounts of time necessary for making boreholes in these points — they are equal to $ t_{1},t _{2} \dots t _{n} $ respectively. You should create such a plan of drilling, that the time necessary to identify the oil reservoir’s boundary is shortest possible, assuming the worst-case scenario.

The first line of the standard input contains a single positive integer $n(1\le n\le 2000)$. The second line contains n positive integers $t_1, t_2, \dots , t_n$ separated by single spaces ($1 \le t _{i} \le 10 ^{6} $).

Your program should write a single integer to the standard output—the smallest amount of time that Byteman has to spend (assuming the worst-case scenario) drilling in search of oil, to be sure that he will identify the reservoir's boundary.