Switch

Interview

Time limit1sMemory limit1024 MB

Summary

Choose windows of three consecutive seconds, none overlapping, to double their points, and find the maximum total score.

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

Problem

At second $i$ , the game gives $A_i$ points. The game lasts $N$ seconds. To earn extra points, you can press a switch at second $T$ . Pressing it doubles the points earned at seconds $T$ , $T+1$ , and $T+2$ . After you press the switch at second $T$ , you can press it again starting from second $T+3$ .

Find the maximum total score you can earn by pressing the switch appropriately while the game runs.

Input

The first line contains the number of scoring seconds $N$ . $\left( 3 \leq N \leq 200\,000 \right)$

The second line contains the integers $A_i$ for each second $i$ , separated by spaces. $\left( 1 \leq i \leq N;\ |A_i| \leq 1000 \right)$

Output

Print the maximum total score you can earn.

Examples4

Example 1
Input
```
3
-2 0 1
```
Expected output
```
0
```
Example 2
Input
```
4
1 2 3 4
```
Expected output
```
20
```
Example 3
Input
```
5
-1 -2 -3 -4 -5
```
Expected output
```
-15
```
Example 4
Input
```
9
-2 10 2 -7 9 1 -2 -3 4
```
Expected output
```
34
```