KOI 호숫가에 여러 개미가 모여 사는 개미굴이 있다.

개미굴은 둥근 호수의 둘레를 따라 1부터 N까지의 번호가 붙은 N개의 방이 차례대로 원형으로 배치되어 있으며,

모든 i (1 ≤ i ≤ N - 1)에 대해 i번째 방과 i + 1번째 방이, 그리고 N번째 방과 1번 째 방이 통로로 직접 연결되어 있는 형태였다.

하지만 여러 이유로 인해 각 방에서 몇 개의 쪽방이 갈라지기 시작해서,
현재는 모든 i ( 1 ≤ i ≤ N)에 대해, 개미굴의 i번째 방에 C_i개의 쪽방이 통로로 직접 연결되어 있다.

i번째 방과 연결된 쪽방은 i번째 방 이외에 다른 방과 통로로 연결되어 있지 않다.

예를 들어 N = 7이고, C = [3, 0, 0, 1, 0, 2, 0]이 인 개미굴은 아래 그림과 같은 형태이다.

개미굴의 각 방과 쪽방에는 최대 한 마리의 개미가 살 수 있다.

만약 통로로 직접 연결 되어 있는 두 곳(방 또는 쪽방) 모두에 개미가 살고 있다면, 두 개미는 서로 불편해한다.

이러한 불편함을 방지하기 위해, 현재 개미굴의 각 통로가 직접 연결하는 두 곳 중 최대 한 곳에만 개미가 살고 있다.

개미들은 똑똑하기 때문에, 이 조건을 만족하는 하에 최대한 많은 수의 개미들이 현재 개미굴에 살고 있다고 한다.

현재 개미굴의 구조가 주어질 때, 개미굴에 살고 있는 개미의 수를 구하는 프로그램을 작성하라.

호숫가의 개미굴 timer 2s memory 1024MB

호숫가의 개미굴 2s 1024MB