독수리

독수리는 양을 먹으며 산다. 양이 사는 곳은 크기가 $1 \times N$인 직사각형이고, $1 \times 1$ 크기의 칸으로 나누어져 있다. 칸은 왼쪽에서부터 $1, 2, \dots, N$번으로 번호가 매겨져 있다. $i$번 칸에 사는 양의 수는 $A_i$마리이다.

독수리는 매일 아침 양을 먹으러 간다. $1$번 칸의 왼쪽이나 $N$번 칸의 오른쪽에서 날기 시작해 먹으려는 양이 있는 칸까지 날아간다. 독수리는 칸을 벗어나서 날 수 없다. 먹으려는 양이 있는 곳이 $x$번이라면, $x$번까지 날아간 다음 $x$번 칸에 있는 양을 모두 먹는다. 독수리는 하루에 한 칸에 있는 양만 먹을 수 있다.

양은 독수리를 매우 무서워하기 때문에 독수리가 나는 모습을 보면 도망간다. 양은 자기 칸 위로 독수리가 나는 것을 확인하면 도망간다. 양이 도망가면 그 칸에 있는 양의 수는 0마리가 된다. 예를 들어 $1$번 칸의 왼쪽에서 날기 시작해 $x$번 칸에 도착했다면 $1$번부터 $x-1$번 칸까지에 있던 양이 모두 도망가 0마리가 된다. $N$번 칸의 오른쪽에서 날기 시작했다면 $x+1$번 칸부터 $N$번 칸까지에 있던 양이 모두 도망간다.

또한 이곳은 위험한 곳이기 때문에 매일 밤에 모든 칸에 있던 양의 수가 1마리씩 줄어든다.

독수리가 매일 어떤 칸에 있는 양을 먹는지와 어느 쪽에서 날기 시작하는지에 따라 먹을 수 있는 양의 수가 달라진다.

양의 수가 주어졌을 때, 독수리가 먹을 수 있는 양의 수의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 칸의 개수 $N$이 주어진다. ($1 \le N \le 1{,}000$)

둘째 줄에 각 칸에 있는 양의 수 $A_1, A_2, \dots, A_N$이 주어진다. ($0 \le A_i \le 100{,}000$)

첫째 줄에 독수리가 먹을 수 있는 양의 최대 수를 출력한다.