Bob is trying to solve Kirito's favourite problem, Maintaining a Sequence! He decides that he must first explore some properties of integer sequences in order to solve it. Bob has a sequence ~a~, consisting of ~N~ integers. He wants to add some of the elements together to obtain the maximum sum possible. However, to make this problem more challenging, Bob decides that he will not add two consecutive elements to his total. In other words, Bob wants to find a subset of his sequence that yields the maximum sum while not containing any adjacent elements.

Note: this subset can be empty, in which case the sum is 0.

Constraints

~1 \le N \le 10^6~
~-10^9 \le a_i \le 10^9~

Input Specification

The first line contains one integer, ~N~, the number of elements in the sequence.
The second line contains ~N~ space-separated integers, ~a_i~, the elements of the sequence.

Sample Input

6
1 3 -2 5 -7 10

Sample Output

18