You are given sequence a_1, a_2, ..., 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^5).

The second line contains n integer numbers a_1, a_2, ..., a_{n} ( - 10^4 ≤ a_{i} ≤ 10^4). 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.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
res = 0
new_a = []
for i in range(n):
    if a[i] % 2 == 0:
        if a[i] > 0:
            res += a[i]
    else:
        new_a.append(a[i])
a = new_a
a.sort()
res += a[-1]
a.pop()
while len(a) > 1:
    if a[-1] + a[-2] > 0:
        res += a[-1] + a[-2]
        a.pop()
        a.pop()
    else:
        break
print(res)

n = int(input())
A = list(map(int, input().split()))
dp = [[-9999999999, -9999999999]]
for elem in A:
    dp += [[0, 0]]
    if elem % 2 == 0:
        dp[-1][0] = max(dp[-2][0] + elem, dp[-2][0], elem)
        dp[-1][1] = max(dp[-2][1] + elem, dp[-2][1])
    else:
        dp[-1][0] = max(dp[-2][1] + elem, dp[-2][0])
        dp[-1][1] = max(dp[-2][0] + elem, dp[-2][1], elem)
print(dp[-1][1])


#!/bin/python3
import sys
import math
n = int(input())
a = list(map(int, input().split()))
even = 0
odds = []
for i in range(n):
    if a[i] % 2 == 0 and a[i] > 0:
        even += a[i];
    elif a[i] % 2 == 1:
        odds.append(-a[i]);
odds.sort()
maxsum = -odds[0]
i = 1
cursum = -odds[0];
while i < len(odds):
    cursum += -(odds[i])
    i += 1
    if i >= len(odds):
        break;
    cursum += -(odds[i])
    i+=1
    maxsum = max(maxsum, cursum)
print(maxsum + even)

n = int(input())
a = list(map(int, input().split()))

f = 0
for i in range(n):
    if a[i] >= 0:
        f += a[i]

if f % 2:
    print(f)
else:
    m = 10 ** 9
    for i in range(n):
        if a[i] % 2:
            m = min(m, abs(a[i]))
            
    print(f - m)

n = int(input())
a = list(map(int, input().split()))
c = list([x for x in a if x % 2 == 0 and x > 0])
b = list([x for x in a if x % 2 != 0])
b = sorted(b, reverse=True)
mm = int(-1e10)
s = 0
for i in range(len(b)):
    s += b[i]
    if i % 2 == 0:
        mm = max(mm, s)
# print(c)
print(sum(c) + mm)


def max(a, b):
	if a > b:
		return a
	else:
		return b

def min(a, b):
	if a < b:
		return a
	else:
		return b

def __starting_point():
	n = int(input())
	A = input().split(' ')
	ans, count, Min, Max = 0, 0, 1000000000, -100000000000
	for i in range(n):
		now = int(A[i])
		if now % 2 == 0:
			ans += max(now, 0)
		else:
			if (now < 0):
				Max = max(Max, now)
			else:
				Min = min(Min, now)
				ans += now

	if ans % 2 == 0:
		ans = max(ans - Min, ans + Max)
	print(ans)

__starting_point()

N = int( input() )
A = list( map( int, input().split() ) )
dp = [ [ - int( 1e9 ) for i in range( 2 ) ] for j in range( N + 1 ) ]
dp[ 0 ][ 0 ] = 0
for i in range( N ):
  for j in range( 2 ):
    if abs( A[ i ] ) & 1:
      dp[ i + 1 ][ j ] = max( dp[ i ][ j ], dp[ i ][ j ^ 1 ] + A[ i ] )
    else:
      dp[ i + 1 ][ j ] = max( dp[ i ][ j ], dp[ i ][ j ] + A[ i ] )
print( dp[ N ][ 1 ] )


n = int(input())
a = list(map(int, input().split()))
a.sort(key=lambda x: -x)
s_p = sum([x for x in a if x > 0])
if s_p % 2 == 1:
    print(s_p)
else:
    m_p = list([x for x in a if x > 0 and x % 2 == 1])
    m_n = list([x for x in a if x < 0 and x % 2 == 1])    
    if len(m_p) > 0 and len(m_n) > 0:
        s_p += max(-min(m_p), max(m_n))
    elif len(m_p) == 0 and len(m_n) > 0:
        s_p += max(m_n)
    else:
        s_p += -min(m_p)
    print(s_p)



_ = input()
v = [int(x) for x in input().split()]

neg_par = []
neg_impar = []
poz_par = []
poz_impar = []

for x in v:
    if x < 0:
        if x % 2 == 0:
            neg_par.append(x)
        else:
            neg_impar.append(x)
    else:
        if x % 2 == 0:
            poz_par.append(x)
        else:
            poz_impar.append(x)

neg_par.sort()
neg_impar.sort()
poz_par.sort()
poz_impar.sort()

res = sum(poz_par)
if len(poz_impar) > 0:
    if len(poz_impar) % 2 == 1:
        res += sum(poz_impar)
    else:
        if len(neg_impar) > 0 and neg_impar[-1] + poz_impar[0] > 0:
            res += sum(poz_impar)
            res += neg_impar[-1]
        else:
            res += sum(poz_impar[1:])
else:
    res += neg_impar[-1]
print(res)


input()
a=[int(x) for x in input().split()]

oc=0
ps=0
pmo=1e6
nmo=-1e6

for x in a:
    if x>0:
        ps+=x
    if x%2==1 and x>0 and pmo>x:
        pmo=x
    if x%2==1 and x>0:    
        oc+=1
    if x%2==1 and x<0 and nmo<x:
        nmo=x

if oc%2==1:
    print(ps)
else:
    print(max(ps-pmo,ps+nmo))

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
i = 0
m1 = float('inf')
m2 = -float('inf')
while i < n and a[i] >= 0:
    if a[i] % 2 == 1:
        m1 = a[i]
    i += 1
s = sum(a[:i])
if s % 2 == 1:
    print(s)
else:
    while i < n and a[i] % 2 == 0:
        i += 1
    if i < n: m2 = a[i]
    print(max(s-m1,s+m2))

n = int(input())
lst = [int(x) for x in input().split(" ")]

even = list([x for x in lst if x % 2 == 0])
odd = list([x for x in lst if x % 2 != 0])

even_sum = 0
for i in even:
    if i > 0:
        even_sum += i # always take all even sums

odd = reversed(sorted(odd))

possible = []
rolling = 0
for i in odd: # there must be at least one odd number
    rolling += i
    possible.append(even_sum + rolling)

possible = reversed(sorted(possible))
for i in possible: # print highest sum
    if i % 2 != 0:
        print(i)
        break


import math
n = int(input())

l = list(map(int, input().split(" ")))
li = []
for i in l:
    if(i > 0):
        li.append(i)
s = sum(li)
found = False
if(s%2 == 0):
    m = 10000
    for i in li:
        if i < m and i%2==1:
            m = i
            found = True
    if(found):    
        m2 = -10000
        for i in l:
            if i > m2 and i < 0 and i%2 == 1:
                m2 = i
        if(abs(m2) > m):
            print(s-m)
        else:
            print(s+m2)
    else:
        m2 = -10000
        for i in l:
            if i > m2 and i < 0 and i%2 == 1:
                m2 = i
        print(s+m2)
else:
    print(s)
    
    
        


n = int(input())
a = [int(i) for i in input().split()]
otrmax = -10**4 - 1
polmin = 10**4 +1
sm = 0
for i in a:
	if i<0:
		if i>otrmax and i%2==1:
			otrmax = i
	else:
		if i<polmin and i%2==1:
			polmin = i
		sm += i

if sm%2==0:
	vrs = []
	if polmin!=10^4 +1:
		vrs.append(sm-polmin)
	if otrmax!=-10^4 - 1:
		vrs.append(sm+otrmax)
	print(max(vrs))
else:
	print(sm)

n=int(input())
a=sorted(list(map(int,input().split())))
mx=max(a)
b=[]
c=[]
d=[]
e=[]
sum1=0
sum2=0
for i in range(n):
    if a[i]>=0:
        sum1+=a[i]
        if a[i]%2==0:
            b.append(a[i])
        else:
            c.append(a[i])
    else:
        sum2+=a[i]
        if a[i]%2==0:
            d.append(a[i])
        else:
            e.append(a[i])
if sum1%2==1 and sum1>0:
    print(sum1)
else:
    if len(e)>0:
        if len(c)>0:
            print(max(sum1+e[-1],sum1-c[0]))
        else:
            print(sum1+e[-1])
    else:
        if len(c)>0:
            print(sum1-c[0])


n=int(input())
a=list(map(int,input().split()))
s=0
b=0
c=0
for i in a:
    if i>0:
        s+=i
        if i%2!=0:
            if b>0:
                b=min(b,i)
            if b==0:
                b=i
    if i<0 and i%2!=0:
        if c<0:
            c=max(c,i)
        if c==0:
            c=i
if s%2!=0:
    print(s)
else:
    if (abs(c)<b or b==0) and c!=0:
        s=s+c
    else:
        s=s-b
    print(s)

import math
(n)=list(map(int,input().split()))
alist=list(map(int,input().split()))
sumpos=0
maxNegOdd=-1e9
maxPosODD=1e9
for i in alist:
    if i>0:
        sumpos+=i
        if i<maxPosODD and i%2!=0:
            maxPosODD=i
    elif i%2!=0 and maxNegOdd<i:
        maxNegOdd=i
if sumpos%2==0:
    if maxPosODD>abs(maxNegOdd):
        sumpos+=maxNegOdd
    else:
        sumpos-=maxPosODD
print(sumpos)


n = int(input())
a = list(map(int, input().split(" ")))

minus_odd = -10001
plus_odd = 10001
total = 0

for i in a:
    if i % 2:
        if i < 0:
            minus_odd = max(minus_odd, i)
        else:
            plus_odd = min(plus_odd, i)

    if i > 0:
        total += i

if total % 2 == 0:
    if minus_odd == -10001:
        print(total - plus_odd)
    elif plus_odd == 10001:
        print(total + minus_odd)
    else:
        if -minus_odd > plus_odd:
            print(total - plus_odd)
        else:
            print(total + minus_odd)

else:
    print(total)

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
s = 0
for i in range(n):
    if a[i] > 0: s += a[i]
    else: break
if s % 2: print(s)
else:
    mx = -100000
    for i in range(n):
        if a[i] < 0 and a[i] % 2: mx = max(a[i], mx)
    mn = 100000
    for i in range(n):
        if a[i] >= 0 and a[i] % 2: mn = min(a[i], mn)
    #print(mx, mn)
    print(max(s + mx, s - mn))


n = int(input())
nums = list(map(int, input().split()))

pos = [x for x in nums if x > 0]
neg = [x for x in nums if x < 0]

s1 = sum(pos)
if s1 % 2 == 1:
    print(s1)
    return

podd = [x for x in pos if x % 2 == 1]
nodd = [x for x in neg if x % 2 == 1]


if podd:
    min_podd = min(podd)
    if not nodd:
        s1 -= min_podd
    else:
        max_nodd = max(nodd)
        if min_podd + max_nodd > 0:
            s1 += max_nodd
        else:
            s1 -= min_podd
else:
    s1 += max(nodd)


print(s1)


n = int(input())
nums = [int(i) for i in input().split()]
result = 0
min_positive = 10001
max_negative = -10001
for i in nums:
    if i > 0:
        result += i
    if i % 2 == 1:
        if 0 < i < min_positive:
            min_positive = i
        elif max_negative < i < 0:
            max_negative = i
if result % 2 == 0:
    if abs(max_negative) > min_positive:
        result -= min_positive
    else:
        result += max_negative
print(result)


n = int(input())
a = list(map(int,input().split()))
s=0
neg = -10000
pos = 10000
for i in range(n):
	if a[i]%2:
		if a[i]<0:
			neg = max(a[i],neg)
		else:
			pos = min(a[i],pos)
	if a[i]>0:s += a[i]
if neg%2 == 0: neg = 10000
if pos%2 == 0: pos = 10000
if s%2==0:
	s-=min(abs(neg),pos)
print(s)


n = int(input())
a = list(map(int,input().split()))
s=0
neg = -10000
pos = 10000
for i in range(n):
	if a[i]%2:
		if a[i]<0:
			neg = max(a[i],neg)
		else:
			pos = min(a[i],pos)
	if a[i]>0:s += a[i]
if neg%2 == 0: neg = 10000
if pos%2 == 0: pos = 10000
if s%2==0:
	s-=min(abs(neg),pos)
print(s)


#! /bin/python
n = int(input())
tab = list(map(int, input().split()))
tab = sorted(tab, reverse=True)
#  print(tab)
maxi = 0
tmpOdd = 0
maxOdd = 0
oddFirst = True
for i in tab:
    if i % 2 == 0 and i > 0:
        maxi += i
    elif i %2 == 1:
        tmpOdd += i
        if tmpOdd % 2 == 1:
            if maxOdd < tmpOdd or oddFirst:
                oddFirst = False
                maxOdd = tmpOdd
maxi += maxOdd
print(maxi)


n=int(input())
s=input()
s=s.split()
l=[]
o=[]
on=[]
sum=0
for i in s:
	te=int(i)
	l.append(te)
	if(te>0 and te%2==1):
		o.append(te)
	elif(te>0 and te%2==0):
		sum+=te
	elif(te<0 and te%2==1):
		on.append(te)
o.sort(reverse=True)
on.sort(reverse=True)
ko=0
for i in on:
	if(i%2==1):
		ko=i
		break

j=2
sumo=0
if(len(o)>0):
	sumo=o[0]
while(j<len(o)):
	sumo+=o[j]+o[j-1]
	j+=2
	

if(len(o)==0):
	print(sum+ko)
elif(len(o)%2==1):
	print(sum+sumo)
elif(len(o)%2==0):
	if(len(on)>0 and ko<0):
		print(max(sum+sumo,sum+sumo+ko+o[-1]))
	elif(len(on)>0 and ko==0):
		print(sum+sumo)
	else:
		print(sum+sumo)