Alice and Bob are playing yet another card game. This time the rules are the following. There are n cards lying in a row in front of them. The i-th card has value a_i. 

First, Alice chooses a non-empty consecutive segment of cards [l; r] (l ≤ r). After that Bob removes a single card j from that segment (l ≤ j ≤ r). The score of the game is the total value of the remaining cards on the segment (a_l + a_{l + 1} + ... + a_{j - 1} + a_{j + 1} + ... + a_{r - 1} + a_r). In particular, if Alice chooses a segment with just one element, then the score after Bob removes the only card is 0.

Alice wants to make the score as big as possible. Bob takes such a card that the score is as small as possible.

What segment should Alice choose so that the score is maximum possible? Output the maximum score.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of cards.

The second line contains n integers a_1, a_2, ..., a_n (-30 ≤ a_i ≤ 30) — the values on the cards.

Output

Print a single integer — the final score of the game.

Examples

Input


5
5 -2 10 -1 4


Output


6


Input


8
5 2 5 3 -30 -30 6 9


Output


10


Input


3
-10 6 -15


Output


0

Note

In the first example Alice chooses a segment [1;5] — the entire row of cards. Bob removes card 3 with the value 10 from the segment. Thus, the final score is 5 + (-2) + (-1) + 4 = 6.

In the second example Alice chooses a segment [1;4], so that Bob removes either card 1 or 3 with the value 5, making the answer 5 + 2 + 3 = 10.

In the third example Alice can choose any of the segments of length 1: [1;1], [2;2] or [3;3]. Bob removes the only card, so the score is 0. If Alice chooses some other segment then the answer will be less than 0.
#include <bits/stdc++.h>
using namespace std;
long long int mod = 998244353;
long long int INF = 1e18;
struct va {
  int sum = 0, left = 0, right = 0, ms = 0;
};
long long int po(long long int a, long long int b) {
  long long int re = 1;
  while (b) {
    if (b % 2 == 1) {
      re = (re * a);
      re %= mod;
    }
    a = (a * a);
    a %= mod;
    b >>= 1;
  }
  return re;
}
vector<int> pos[61];
int in[61];
int ans = 0;
int a[100001];
va dnc(int l, int r, int n) {
  va res, t, tem;
  if (l > r || n == -1) return res;
  if (l == r) {
    res.sum = res.ms = a[l];
    if (a[l] > 0) {
      res.left = res.right = a[l];
    }
    in[a[l] + 30]++;
    return res;
  }
  bool f = 1;
  n++;
  while (f) {
    n--;
    int o = in[n];
    for (int i = (o); i < (pos[n].size()); i++) {
      if (pos[n][i] > r) break;
      f = 0;
      in[n]++;
      if (i == o) {
        res = dnc(l, pos[n][i] - 1, n - 1);
      } else {
        t = dnc(pos[n][i - 1] + 1, pos[n][i] - 1, n - 1);
        tem.sum = res.sum + t.sum + n - 30;
        tem.left = max(res.left, res.sum + t.left + n - 30);
        tem.right = max(t.right, t.sum + res.right + n - 30);
        tem.ms = max(res.right + t.left + n - 30, max(res.ms, t.ms));
        res = tem;
      }
    }
  }
  t = dnc(pos[n][in[n] - 1] + 1, r, n - 1);
  tem.sum = res.sum + t.sum + n - 30;
  tem.left = max(res.left, res.sum + t.left + n - 30);
  tem.right = max(t.right, t.sum + res.right + n - 30);
  tem.ms = max(res.right + t.left + n - 30, max(res.ms, t.ms));
  res = tem;
  if (n > 30) ans = max(ans, (res.ms - (n - 30)));
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int test = 1;
  while (test--) {
    int n;
    cin >> n;
    for (int i = (0); i < (n); i++) {
      cin >> a[i];
      pos[a[i] + 30].push_back(i);
    }
    va f = dnc(0, n - 1, 60);
    cout << ans;
  }
  return 0;
}
