#include <bits/stdc++.h>
using namespace std;
enum enum_t { White, Black, Gray };
inline int readInt() {
  char c;
  while (c = getchar(), c != '-' && (c < '0' || c > '9'))
    ;
  bool sign = (c == '-');
  if (sign) c = getchar();
  int n = c - '0';
  while (c = getchar(), c >= '0' && c <= '9') n = 10 * n + c - '0';
  return (!sign) ? n : -n;
}
inline long long readLong() {
  char c;
  while (c = getchar(), c != '-' && (c < '0' || c > '9'))
    ;
  bool sign = (c == '-');
  if (sign) c = getchar();
  long long n = c - '0';
  while (c = getchar(), c >= '0' && c <= '9') n = 10 * n + c - '0';
  return (!sign) ? n : -n;
}
inline void getInt(int &n) {
  char c;
  while (c = getchar(), c != '-' && (c < '0' || c > '9'))
    ;
  bool sign = (c == '-');
  if (sign) c = getchar();
  n = c - '0';
  while (c = getchar(), c >= '0' && c <= '9') n = 10 * n + c - '0';
  if (sign) n = -n;
}
inline void getLong(long long &n) {
  char c;
  while (c = getchar(), c != '-' && (c < '0' || c > '9'))
    ;
  bool sign = (c == '-');
  if (sign) c = getchar();
  n = c - '0';
  while (c = getchar(), c >= '0' && c <= '9') n = 10 * n + c - '0';
  if (sign) n = -n;
}
inline string readString() {
  char c;
  while (c = getchar(), c == ' ' || c == '\n' || c == '\t')
    ;
  string s({c});
  while (c = getchar(), c != EOF && c != ' ' && c != '\n' && c != '\t') s += c;
  return s;
}
char bufWrite[20];
template <typename T>
inline void writeInt(T x) {
  if (x < 0) putchar('-'), x = -x;
  char *bufPos = bufWrite;
  do {
    *bufPos++ = x % 10 + '0';
  } while (x /= 10);
  do {
    putchar(*--bufPos);
  } while (bufPos > bufWrite);
}
template <typename T>
inline void printInt(T x, char c = EOF) {
  if (x < 0) putchar('-'), x = -x;
  char *bufPos = bufWrite;
  do {
    *bufPos++ = x % 10 + '0';
  } while (x /= 10);
  do {
    putchar(*--bufPos);
  } while (bufPos > bufWrite);
  if (c != EOF) putchar(c);
}
template <typename T>
inline T gcd(T a, T b) {
  while (b != 0) swap(b, a %= b);
  return a;
}
template <typename T>
inline T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template <typename T>
inline tuple<T, T, T> extgcd(T a, T b) {
  if (!a) return make_tuple(b, 0, 1);
  T g, x, y;
  tie(g, x, y) = extgcd(b % a, a);
  return make_tuple(g, y - (b / a) * x, x);
}
template <class T>
T bitGet(T x, int bit) {
  return T(1) & (x >> (bit - 1));
}
template <class T>
void bitSet(T &x, int bit) {
  x |= (T(1) << (bit - 1));
}
template <class T>
void bitReset(T &x, int bit) {
  x &= ~(T(1) << (bit - 1));
}
template <class T>
void bitFlip(T &x, int bit) {
  x ^= (T(1) << (bit - 1));
}
template <class T>
void bitMake(T &x, int bit, bool val) {
  x ^= (T(1) << (bit - 1)) & (-val ^ x);
}
const long long LINF = (1LL << 60);
const int INF = (1 << 30);
const int LIM = (1 << 24);
const int MOD = 1e9 + 7;
const int BASE = 1e4;
const int DIGIT = 4;
int query() { return 0; }
int main() {
  int n = readInt();
  int posi_odd_cnt = 0;
  int posi_odd_min = +INF;
  int posi_odd_sum = -INF;
  int posi_eve_sum = -INF;
  int nega_odd_max = -INF;
  int nega_eve_max = -INF;
  for (int i = 0; i < n; ++i) {
    int x = readInt();
    if (x > 0) {
      if (x & 1) {
        posi_odd_sum = max(posi_odd_sum + x, x);
        posi_odd_min = min(posi_odd_min, x);
        posi_odd_cnt++;
      } else
        posi_eve_sum = max(posi_eve_sum + x, x);
    } else
      (x & 1) ? nega_odd_max = max(nega_odd_max, x)
              : nega_eve_max = max(nega_eve_max, x);
  }
  int res = max(0, posi_eve_sum);
  res +=
      (posi_odd_cnt & 1)
          ? max(posi_odd_sum, nega_odd_max)
          : max(max(posi_odd_sum + nega_odd_max, posi_odd_sum - posi_odd_min),
                nega_odd_max);
  cout << res;
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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;
enum enum_t { White, Black, Gray };
inline int readInt() {
  char c;
  while (c = getchar(), c != '-' && (c < '0' || c > '9'))
    ;
  bool sign = (c == '-');
  if (sign) c = getchar();
  int n = c - '0';
  while (c = getchar(), c >= '0' && c <= '9') n = 10 * n + c - '0';
  return (!sign) ? n : -n;
}
inline long long readLong() {
  char c;
  while (c = getchar(), c != '-' && (c < '0' || c > '9'))
    ;
  bool sign = (c == '-');
  if (sign) c = getchar();
  long long n = c - '0';
  while (c = getchar(), c >= '0' && c <= '9') n = 10 * n + c - '0';
  return (!sign) ? n : -n;
}
inline void getInt(int &n) {
  char c;
  while (c = getchar(), c != '-' && (c < '0' || c > '9'))
    ;
  bool sign = (c == '-');
  if (sign) c = getchar();
  n = c - '0';
  while (c = getchar(), c >= '0' && c <= '9') n = 10 * n + c - '0';
  if (sign) n = -n;
}
inline void getLong(long long &n) {
  char c;
  while (c = getchar(), c != '-' && (c < '0' || c > '9'))
    ;
  bool sign = (c == '-');
  if (sign) c = getchar();
  n = c - '0';
  while (c = getchar(), c >= '0' && c <= '9') n = 10 * n + c - '0';
  if (sign) n = -n;
}
inline string readString() {
  char c;
  while (c = getchar(), c == ' ' || c == '\n' || c == '\t')
    ;
  string s({c});
  while (c = getchar(), c != EOF && c != ' ' && c != '\n' && c != '\t') s += c;
  return s;
}
char bufWrite[20];
template <typename T>
inline void writeInt(T x) {
  if (x < 0) putchar('-'), x = -x;
  char *bufPos = bufWrite;
  do {
    *bufPos++ = x % 10 + '0';
  } while (x /= 10);
  do {
    putchar(*--bufPos);
  } while (bufPos > bufWrite);
}
template <typename T>
inline void printInt(T x, char c = EOF) {
  if (x < 0) putchar('-'), x = -x;
  char *bufPos = bufWrite;
  do {
    *bufPos++ = x % 10 + '0';
  } while (x /= 10);
  do {
    putchar(*--bufPos);
  } while (bufPos > bufWrite);
  if (c != EOF) putchar(c);
}
template <typename T>
inline T gcd(T a, T b) {
  while (b != 0) swap(b, a %= b);
  return a;
}
template <typename T>
inline T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template <typename T>
inline tuple<T, T, T> extgcd(T a, T b) {
  if (!a) return make_tuple(b, 0, 1);
  T g, x, y;
  tie(g, x, y) = extgcd(b % a, a);
  return make_tuple(g, y - (b / a) * x, x);
}
template <class T>
T bitGet(T x, int bit) {
  return T(1) & (x >> (bit - 1));
}
template <class T>
void bitSet(T &x, int bit) {
  x |= (T(1) << (bit - 1));
}
template <class T>
void bitReset(T &x, int bit) {
  x &= ~(T(1) << (bit - 1));
}
template <class T>
void bitFlip(T &x, int bit) {
  x ^= (T(1) << (bit - 1));
}
template <class T>
void bitMake(T &x, int bit, bool val) {
  x ^= (T(1) << (bit - 1)) & (-val ^ x);
}
const long long LINF = (1LL << 60);
const int INF = (1 << 30);
const int LIM = (1 << 24);
const int MOD = 1e9 + 7;
const int BASE = 1e4;
const int DIGIT = 4;
int query() { return 0; }
int main() {
  int n = readInt();
  int posi_odd_cnt = 0;
  int posi_odd_min = +INF;
  int posi_odd_sum = -INF;
  int posi_eve_sum = -INF;
  int nega_odd_max = -INF;
  int nega_eve_max = -INF;
  for (int i = 0; i < n; ++i) {
    int x = readInt();
    if (x > 0) {
      if (x & 1) {
        posi_odd_sum = max(posi_odd_sum + x, x);
        posi_odd_min = min(posi_odd_min, x);
        posi_odd_cnt++;
      } else
        posi_eve_sum = max(posi_eve_sum + x, x);
    } else
      (x & 1) ? nega_odd_max = max(nega_odd_max, x)
              : nega_eve_max = max(nega_eve_max, x);
  }
  int res = max(0, posi_eve_sum);
  res +=
      (posi_odd_cnt & 1)
          ? max(posi_odd_sum, nega_odd_max)
          : max(max(posi_odd_sum + nega_odd_max, posi_odd_sum - posi_odd_min),
                nega_odd_max);
  cout << res;
  return 0;
}

```