#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1000000000 + 7;
const long long int MOD1 = 998244353;
long long int nCr(long long int n, long long int r) {
  long long int ans = 1;
  for (long long int i = (long long int)0; i < (long long int)r; i++) {
    ans = (ans * (n - i));
    ans = (ans / (i + 1));
  }
  return ans;
}
vector<long long int> adj[300010];
vector<long long int> v3;
bool vis[300010];
map<long long int, long long int> mp;
vector<long long int> vv[300010];
long long int ans[300010];
void dfs(long long int sr, long long int cl) {
  vis[sr] = true;
  for (long long int i = (long long int)0; i < (long long int)adj[sr].size();
       i++) {
    if (!vis[adj[sr][i]]) {
      if (ans[sr] == 1) {
        ans[adj[sr][i]] = 2;
        dfs(adj[sr][i], 2);
      } else {
        ans[adj[sr][i]] = 1;
        dfs(adj[sr][i], 1);
      }
    }
  }
}
vector<pair<long long int, long long int>> v1[1010];
long long int dis[1010];
bool prc[1010];
long long int fr[1010][1010];
void dik(long long int sr) {
  for (long long int i = (long long int)0; i < (long long int)1010; i++)
    dis[i] = 1e18;
  for (long long int i = (long long int)0; i < (long long int)1010; i++)
    prc[i] = false;
  dis[sr] = 0;
  priority_queue<pair<long long int, long long int>> q;
  q.push({0, sr});
  fr[sr][sr] = 0;
  while (!q.empty()) {
    long long int a = q.top().second;
    q.pop();
    if (prc[a]) continue;
    prc[a] = true;
    for (auto it : v1[a]) {
      long long int b = it.first;
      long long int w = it.second;
      if (dis[a] + w < dis[b]) {
        dis[b] = dis[a] + w;
        q.push({-dis[b], b});
        fr[sr][b] = dis[b];
      }
    }
  }
}
long long int par[500005];
long long int rk[500005];
long long int e[500005];
long long int fin(long long int sr) {
  if (par[sr] == sr) return sr;
  return par[sr] = fin(par[sr]);
}
void unin(long long int a, long long int b) {
  a = fin(a);
  b = fin(b);
  if (rk[a] < rk[b]) {
    par[a] = par[b];
    rk[b] += rk[a];
    rk[a] = rk[b];
  } else {
    par[b] = par[a];
    rk[a] += rk[b];
    rk[b] = rk[a];
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  long long int n;
  cin >> n;
  long long int a[n];
  long long int sum = 0;
  for (long long int i = (long long int)0; i < (long long int)n; i++) {
    cin >> a[i];
    if (a[i] > 0) sum += a[i];
  }
  if (sum % 2 != 0)
    cout << sum << "\n";
  else {
    long long int mi = 1e18;
    long long int ans = sum;
    for (long long int i = (long long int)0; i < (long long int)n; i++) {
      if (a[i] > 0 && a[i] & 1) mi = min(mi, a[i]);
    }
    ans = sum - mi;
    for (long long int i = (long long int)0; i < (long long int)n; i++) {
      if (a[i] < 0 && a[i] & 1) ans = max(ans, sum + a[i]);
    }
    cout << ans << "\n";
  }
  cerr << "Time Elapsed : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC
       << "ms\n";
  return 0;
}

### Prompt

Please formulate a cpp solution 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 long long int MOD = 1000000000 + 7;
const long long int MOD1 = 998244353;
long long int nCr(long long int n, long long int r) {
  long long int ans = 1;
  for (long long int i = (long long int)0; i < (long long int)r; i++) {
    ans = (ans * (n - i));
    ans = (ans / (i + 1));
  }
  return ans;
}
vector<long long int> adj[300010];
vector<long long int> v3;
bool vis[300010];
map<long long int, long long int> mp;
vector<long long int> vv[300010];
long long int ans[300010];
void dfs(long long int sr, long long int cl) {
  vis[sr] = true;
  for (long long int i = (long long int)0; i < (long long int)adj[sr].size();
       i++) {
    if (!vis[adj[sr][i]]) {
      if (ans[sr] == 1) {
        ans[adj[sr][i]] = 2;
        dfs(adj[sr][i], 2);
      } else {
        ans[adj[sr][i]] = 1;
        dfs(adj[sr][i], 1);
      }
    }
  }
}
vector<pair<long long int, long long int>> v1[1010];
long long int dis[1010];
bool prc[1010];
long long int fr[1010][1010];
void dik(long long int sr) {
  for (long long int i = (long long int)0; i < (long long int)1010; i++)
    dis[i] = 1e18;
  for (long long int i = (long long int)0; i < (long long int)1010; i++)
    prc[i] = false;
  dis[sr] = 0;
  priority_queue<pair<long long int, long long int>> q;
  q.push({0, sr});
  fr[sr][sr] = 0;
  while (!q.empty()) {
    long long int a = q.top().second;
    q.pop();
    if (prc[a]) continue;
    prc[a] = true;
    for (auto it : v1[a]) {
      long long int b = it.first;
      long long int w = it.second;
      if (dis[a] + w < dis[b]) {
        dis[b] = dis[a] + w;
        q.push({-dis[b], b});
        fr[sr][b] = dis[b];
      }
    }
  }
}
long long int par[500005];
long long int rk[500005];
long long int e[500005];
long long int fin(long long int sr) {
  if (par[sr] == sr) return sr;
  return par[sr] = fin(par[sr]);
}
void unin(long long int a, long long int b) {
  a = fin(a);
  b = fin(b);
  if (rk[a] < rk[b]) {
    par[a] = par[b];
    rk[b] += rk[a];
    rk[a] = rk[b];
  } else {
    par[b] = par[a];
    rk[a] += rk[b];
    rk[b] = rk[a];
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  long long int n;
  cin >> n;
  long long int a[n];
  long long int sum = 0;
  for (long long int i = (long long int)0; i < (long long int)n; i++) {
    cin >> a[i];
    if (a[i] > 0) sum += a[i];
  }
  if (sum % 2 != 0)
    cout << sum << "\n";
  else {
    long long int mi = 1e18;
    long long int ans = sum;
    for (long long int i = (long long int)0; i < (long long int)n; i++) {
      if (a[i] > 0 && a[i] & 1) mi = min(mi, a[i]);
    }
    ans = sum - mi;
    for (long long int i = (long long int)0; i < (long long int)n; i++) {
      if (a[i] < 0 && a[i] & 1) ans = max(ans, sum + a[i]);
    }
    cout << ans << "\n";
  }
  cerr << "Time Elapsed : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC
       << "ms\n";
  return 0;
}

```