You are given ~N~ cookies that are lined up in a row. Each cookie has a tastiness value, ~a_i~. You want to maximize the sum of the tastiness values of the cookies that you eat. However, you can only eat cookies that are not adjacent to each other.

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 100~ ~000)~.

The second line will contain ~N~ integers, ~a_1, a_2, \ldots, a_N~ ~(1 \le a_i \le 10~ ~000)~.

Output Specification

The maximum sum of the tastiness values of the cookies you eat, satisfying the constraint that you may not eat cookies that are adjacent to one other.

Subtasks

Subtask 1 [10%]

~N \le 10~

Subtask 2 [30%]

~N \le 1~ ~000~

Subtask 3 [60%]

No further constraints.

Sample Input 1

3
1 7 5

Sample Output 1

7

Explanation for Sample 1

The maximum tastiness sum would be to only take the cookie with a tastiness value of ~7~ for a total sum of ~7~.

Sample Input 2

5
1 10 4 7 8

Sample Output 2

18