Lemon Picking

Interview

Time limit2sMemory limit1024 MB

Summary

Seongwoo picks lemons from one tree and walks home, losing one lemon per move. Find the maximum number of lemons he can carry home.

Level: Easy2 of 10
Topics: Implementation, Math
Solved: No attempts yet

Problem

Seongwoo has to pick lemons in a forest. The forest can be drawn as a single number line, and $N$ lemon trees grow at evenly spaced positions from $x=1$ to $x=N$ . Seongwoo is currently at $x=0$ , and his house is at $x=N+1$ . The tree at $x=i$ has $a_i$ lemons. Until he gets home, Seongwoo chooses one of the following actions each time.

Pick: pick all lemons growing on the tree. He can do this action at most once.
Move: if he is at $x=i$ , he moves to $x=i+1$ .

However, the bag he carries lemons in has a hole. Each time he moves (action 2), if the bag holds lemons, one lemon falls out, and it cannot be picked up again. Find the maximum number of lemons Seongwoo can take home.

Input

The first line contains the number of trees $N$ . $(1 \leq N \leq 2 \times 10^5)$

The second line contains the number of lemons $a_i$ on the tree at $x=i$ , in order. $(1 \leq a_i \leq 10^9)$

Output

Print the maximum number of lemons Seongwoo can take home.

Examples2

Example 1
Input
```
3
2 3 4
```
Expected output
```
3
```
Example 2
Input
```
4
100 97 90 12
```
Expected output
```
96
```