Herb Trees

Interview

Time limit1sMemory limit1024 MB

Summary

Pick trees to keep so that no two kept trees are adjacent, maximizing the sum of their berry counts.

Level: Medium4 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

Farmer Ugnė planted $N$ herb trees in her garden. She planted them in a straight line and numbered them in order from $1$ to $N$ .

Unfortunately, as soon as the first berry buds appeared, Ugnė realized that the trees had been planted too densely. If she does nothing, neighboring trees will overshadow one another and she will be left with no berries this year.

To prevent this, Ugnė plans to transplant some of the trees; a transplanted tree bears no fruit this year. If Ugnė wants to keep a tree $i$ , she must transplant both of its neighbors, trees $i-1$ and $i+1$ .

Which trees should Ugnė transplant so that the remaining harvest is as large as possible?

Input

The first line contains the number of trees $N$ .

The second line contains $N$ integers $A_1, A_2, \dots, A_N$ separated by spaces, where $A_i$ is the number of berry buds on tree $i$ .

Output

Output a single integer on one line: the maximum number of berries Ugnė can hope for if she transplants the trees optimally.

Constraints

$1 \le N \le 100000$
$1 \le A_i \le 1000$

Examples2

Example 1
Input
```
4
1 2 2 1
```
Expected output
```
3
```
Example 2
Input
```
4
2 1 1 2
```
Expected output
```
4
```