← 返回题目列表

Codeforces · 797/B

B. 奇数和

中文机器翻译题面 查看原题

给定序列 a1, a2, ..., an,由长度为 n 的整数组成。你的任务是在所有这样的子序列中找到其总和为奇数且最大的子序列。保证给定序列包含奇数和的子序列。

子序列是可以通过删除某些元素而不改变剩余元素的顺序从另一个序列导出的序列。

你应该编写一个程序来找到最佳子序列的总和。

输入

第一行包含整数 n (1 ≤ n ≤ 105)。

第二行包含 n 个整数 a1, a2, ..., an ( - 104 ≤ ai ≤ 104)。该序列至少包含一个具有奇数和的子序列。

输出

打印结果子序列的总和。

示例

输入 #1

4
-2 2 -3 1

输出 #1

3

输入 #2

3
2 -5 -3

输出 #2

-1

注意

在第一个示例中,第二个和第四个元素的总和为 3。