Curious subsequences P92016


Statement
 

pdf   zip

thehtml

In this problem, we will say that a (sub)sequence of integer numbers is curious if it does not have two consecutive numbers whose sum is even. Given a sequence of n integer numbers, what is the maximum sum of elements of all its curious subsequences?

For instance, for 8 10 101 100 120 the maximum sum is 231, corresponding to 10 101 120.

Input

Input consists of several cases, each one with n followed by n integer numbers between −109 and 109. Assume 1 ≤ n ≤ 107.

Output

Print the maximum possible sum for every case.

Public test cases

  • Input

    5  8 10 101 100 120
4  5 5 5 5
1  10
2  -1 -4
3 1000000000 999999999 1000000000

    Output

    231
5
10
0
2999999999
    • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++