跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0808. Odd sum

  • ID: 814
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:基础
  • 上传者:
  • 动态规划
  • 贪心
  • 模拟
  • 算法思想
  • 编程与模拟
  • 基础
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Odd sum

题目描述

B. Odd sum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given sequence a1,a2,...,an 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≤105).

The second line contains n integer numbers a1,a2,...,an (-104≤ai≤104). The sequence contains at least one subsequence with odd sum.

Output

Print sum of resulting subseqeuence.

Examples
Input
4
-2 2 -3 1
Output
3
Input
3
2 -5 -3
Output
-1
Note

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


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 236 题。保留原作者与原赛事署名。