Odd sum

1000ms

262144K

Description:

You are given sequence a₁, a₂, ..., a_n of integer numbers of length n. Your task is to find such subsequence that its sum is odd and maximum among all such subsequences. It's guaranteed that given sequence contains subsequence with odd sum.

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

You should write a program which finds sum of the best subsequence.

Input:

The first line contains integer number n (1 ≤ n ≤ 10⁵).

The second line contains n integer numbers a₁, a₂, ..., a_n ( - 10⁴ ≤ a_i ≤ 10⁴). The sequence contains at least one subsequence with odd sum.

Output:

Print sum of resulting subseqeuence.

Sample Input:

4
-2 2 -3 1

Sample Output:

Sample Input:

3
2 -5 -3

Sample Output:

-1

Note:

In the first example sum of the second and the fourth elements is 3.

Informação

Provedor Codeforces

Código CF797B