외계인의 침공

바이토시아에는 하나의 도로를 따라 $n$개의 도시가 일렬로 놓여 있다. 도로를 왼쪽부터 차례로 보며 도시에 $1$번부터 $n$번까지 번호를 매기고, $i$번 도시에는 $a_i$명의 주민이 산다.

외계인은 언제나 밤에 습격하며, 하룻밤에 많아야 한 도시를 노린다. 습격은 순식간에 끝나서, 공격당한 도시의 주민은 전원 그 즉시 납치되어 외계인의 은하로 끌려간다.

주민을 지키기 위해 과학자들은 훈련된 쥐로 다른 도시에 경보를 전한다. 외계인이 어떤 도시를 공격하면 그 도시에서 쥐 두 마리가 도로의 양쪽 방향으로 달려 나가 습격 소식을 나른다. 도로의 한 구간을 지나는 데 거의 하루가 걸리므로, $j$번 도시에서 출발한 소식은 습격이 있은 뒤 $|k-j|$번째 날 해가 지기 직전에 $k$번 도시에 닿는다. 경보를 받은 주민은 외계인의 촉수가 닿지 않는 대피소로 숨고, 물자가 넉넉한 대피소에서 외계인이 습격을 멈추고 은하로 돌아갈 때까지 머문다.

이 방식만으로는 모든 주민을 구하지 못할 수도 있다. 과학자들은 최악의 경우, 곧 외계인이 납치 인원을 최대로 만들도록 공격했을 때 몇 명이나 납치될 수 있는지 알고 싶어 한다.

첫째 줄에 도시의 수 $n$ ($1 \le n \le 10^6$)이 주어진다.

둘째 줄에 도로를 따라 놓인 각 도시의 주민 수를 나타내는 정수 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$)이 공백으로 구분되어 주어진다.

최악의 경우 납치될 수 있는 주민 수의 최댓값을 정수 하나로 한 줄에 출력한다.