STAIRSTEP

Let's consider a staircase with ~N~ steps and two head steps, one at the bottom and one at the top. An integer number is written on each step. Zero is written on the two head steps. You can climb the staircase starting from the bottom head step until you reach the top head step. At each step, you can climb either one or two steps. As you climb, you add up the numbers written on the steps you step on.

You are asked to find the maximum value of the sum you can form in this way.

Input

The input will consist of two lines. The first line will contain only the natural number N: the number of steps. The second line will contain N integer numbers, separated in pairs by a single space: these numbers are written on the steps, in order from bottom to top. The absolute value of the numbers will not exceed 1000.

Output

The output should consist of one line containing one natural number: the maximum sum you can form.

Constraints

~1 \le N \le 1.000.000~
Execution time limit: 1 sec.
Memory limit: 64 MB.

Examples of Input - Output

1st

STDIN (stairstep.in)

4
5 -3 -1 2

STDOUT (stairstep.out)

6

2nd

STDIN (stairstep.in)

9
-21 -23 -69 -67 1 41 97 49 27

STDOUT (stairstep.out)

125

Explanation of the Examples: Maximum sums are achieved as shown in the following diagrams.