#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9;
const long long LINF = (long long)1e18;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline long long isqrt(long long k) {
  long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
const int maxn = 1e5 + 5;
int n;
int a[maxn];
void solve() {
  if (fopen("in.txt", "r")) {
    freopen("in.txt", "r", stdin);
  }
  cin >> n;
  long long sum = 0;
  for (int i = (0); i < (n); i++) {
    cin >> a[i];
    if (a[i] >= 0) {
      sum += a[i];
    }
  }
  if (sum & 1) {
    cout << sum << "\n";
    return;
  }
  int mn = INF + INF;
  for (int i = (0); i < (n); i++) {
    if ((a[i] & 1) && a[i] >= 0) {
      chkmin(mn, a[i]);
    }
  }
  for (int i = (0); i < (n); i++) {
    if ((a[i] & 1) && a[i] < 0) {
      chkmin(mn, -a[i]);
    }
  }
  cout << sum - mn << "\n";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  cerr << "Time elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}

### Prompt

Please create a solution in cpp to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int INF = (int)1e9;
const long long LINF = (long long)1e18;
const long double PI = acos((long double)-1);
const long double EPS = 1e-9;
inline long long gcd(long long a, long long b) {
  long long r;
  while (b) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long fpow(long long n, long long k, int p = MOD) {
  long long r = 1;
  for (; k; k >>= 1) {
    if (k & 1) r = r * n % p;
    n = n * n % p;
  }
  return r;
}
template <class T>
inline int chkmin(T& a, const T& val) {
  return val < a ? a = val, 1 : 0;
}
template <class T>
inline int chkmax(T& a, const T& val) {
  return a < val ? a = val, 1 : 0;
}
inline long long isqrt(long long k) {
  long long r = sqrt(k) + 1;
  while (r * r > k) r--;
  return r;
}
inline long long icbrt(long long k) {
  long long r = cbrt(k) + 1;
  while (r * r * r > k) r--;
  return r;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline int sign(long double x) { return x < -EPS ? -1 : x > +EPS; }
inline int sign(long double x, long double y) { return sign(x - y); }
const int maxn = 1e5 + 5;
int n;
int a[maxn];
void solve() {
  if (fopen("in.txt", "r")) {
    freopen("in.txt", "r", stdin);
  }
  cin >> n;
  long long sum = 0;
  for (int i = (0); i < (n); i++) {
    cin >> a[i];
    if (a[i] >= 0) {
      sum += a[i];
    }
  }
  if (sum & 1) {
    cout << sum << "\n";
    return;
  }
  int mn = INF + INF;
  for (int i = (0); i < (n); i++) {
    if ((a[i] & 1) && a[i] >= 0) {
      chkmin(mn, a[i]);
    }
  }
  for (int i = (0); i < (n); i++) {
    if ((a[i] & 1) && a[i] < 0) {
      chkmin(mn, -a[i]);
    }
  }
  cout << sum - mn << "\n";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  cerr << "Time elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
  return 0;
}

```