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++