Bob is trying to solve 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.'s favourite problem,
Note: this subset can be empty, in which case the sum is 0.
~1 \le N \le 10^6~
~-10^9 \le a_i \le 10^9~
The first line contains one integer, ~N~, the number of elements in the sequence.
The second line contraints ~N~ space-separated integers, ~a_i~, the elements of the sequence.
6 1 3 -2 5 -7 10