시추

바이트맨(Byteman)은 원유 매장층을 찾는 팀을 이끌고 있다. 팀은 이미 시추공을 두 개 뚫어, 지점 $A$에서는 원유를 발견했고 지점 $B$에서는 원유가 없음을 확인했다. 매장층은 한쪽 끝이 정확히 $A$에 있는, 선분 $AB$의 연결된 한 조각을 차지한다. 이제 바이트맨은 매장층이 $AB$를 따라 어디까지 뻗어 있는지 알아내야 한다.

이 일은 간단하지 않다. 위치마다 시추 속도가 다르고, 팀은 한 번에 한 곳에서만 시추할 수 있기 때문이다. 바이트맨은 최악의 경우 매장층의 경계를 확정하는 데 시간이 얼마나 필요한지 미리 알고 싶어 한다.

선분 $AB$를 길이가 같은 $n + 1$개의 조각으로 나눈다. $A$를 좌표 $0$, $B$를 좌표 $n + 1$에 두면, 후보 지점들은 좌표 $1, 2, \ldots, n$에 놓인다. 원유는 좌표 $0$(지점 $A$)까지는 있지만 좌표 $n + 1$(지점 $B$)에는 없으므로, 경계는 $1, 2, \ldots, n$ 중에서 아직 원유가 있는 가장 큰 좌표이다(그런 좌표가 하나도 없으면 경계는 $0$이다). 지점 $i$에 시추공을 뚫는 데는 $t_i$만큼의 시간이 걸리며, 그곳에 원유가 있는지 없는지를 알려 준다.

최악의 경우 매장층의 경계를 확정하는 데 드는 총 시간을 최소로 만드는 시추 계획을 세우고, 그 시간을 구하라.

첫째 줄에 정수 $n$이 주어진다 ($1 \le n \le 2000$).

둘째 줄에 $n$개의 정수 $t_1, t_2, \ldots, t_n$이 공백 하나로 구분되어 주어진다 ($1 \le t_i \le 10^6$).

바이트맨이 매장층의 경계를 반드시 확정할 수 있게 하는, 최악의 경우 총 시추 시간의 최솟값을 정수 하나로 출력하라.

바이트맨이 지점 $1$을 먼저 시추한다고 하자. 여기에 시간 $8$이 든다. 만약 그곳에서 원유가 나오면 매장층이 오른쪽으로 얼마나 뻗는지를 여전히 알아내야 하고, 이때 최악의 경우 두 번의 시추가 더 필요해 $36$이 들어 합계는 $44$가 된다.

지점 $2$에서 시작하는 편이 더 낫다. 지점 $2$에 원유가 없으면 지점 $1$만 확인하면 끝난다. 원유가 있으면 최악의 경우 지점 $3$과 $4$를 시추하여 총 시간 $42$로 마친다. 따라서 이 예제에서는 $42$가 최적이다.