28061번 - 레몬 따기

성우는 숲에서 레몬을 따와야 한다. 숲은 하나의 수직선으로 표현할 수 있고, 여기에는 레몬 나무 \(N\)그루가 \(x=1\)부터 \(x=N\)까지 일정한 간격으로 자라 있다. 성우는 현재 \(x=0\)에 있으며, 집은 \(x=N+1\)에 있다. \(x=i\)에 위치한 나무에는 \(a_i\)개의 레몬이 자라 있다. 성우는 집에 돌아갈 때까지 매번 다음 중 하나를 선택하여 행동한다.

1. 채집: 나무에 자라있는 레몬을 모두 딴다. 이 행동은 최대 한 번 할 수 있다.
2. 이동: 현재 위치가 \(x=i\)라면, \(x=i+1\)로 이동한다.

하지만 레몬을 담을 보따리에는 구멍이 뚫려 있었다. 성우가 이동(행동 2)할 때마다, 보따리에 레몬이 담겨 있다면 보따리에 담긴 레몬이 \(1\)개 빠져나오고, 이는 다시 주울 수 없다. 성우가 집에 들고 갈 수 있는 레몬의 최대 개수를 구해주자!

첫째 줄에 나무의 수 \(N\)이 주어진다. \((1 \leq N \leq 2 \times 10^5)\)

둘째 줄에는 \(x=i\)에 위치한 나무에 자라 있는 레몬의 개수 \(a_i\)가 차례대로 주어진다. \((1 \leq a_i \leq 10^9)\)

성우가 집에 들고 갈 수 있는 레몬의 최대 개수를 출력한다.