레몬 따기

면접 대비

시간 제한2초메모리 제한1024 MB

요약

세응우가 나무 한 그루에서 레몬을 따서 집까지 걸어갈 때, 이동할 때마다 레몬이 하나씩 빠집니다. 집에 가져갈 수 있는 레몬의 최대 개수를 구합니다.

난이도: 쉬움10점 중 2점
유형: 구현, 수학
정답자: 아직 제출이 없습니다

문제

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

채집: 나무에 자라 있는 레몬을 모두 딴다. 이 행동은 최대 한 번 할 수 있다.
이동: 현재 위치가 $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)$

출력

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

예제2

예제 1
입력
```
3
2 3 4
```
예상 출력
```
3
```
예제 2
입력
```
4
100 97 90 12
```
예상 출력
```
96
```