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 −10^{9} and 10^{9}.
Assume 1 ≤ n ≤ 10^{7}.

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++
- Event
- Quinzè Concurs de Programació de la UPC - Final
- Date
- 2017-09-13