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;
const long long MOD = (long long)1e9 + 7;
const long long MOD1 = 2286661337;
const long long MOD2 = 998244353;
const int INF = (int)1e9 + 7;
const double EPS = 1e-7;
const int N = (int)1e5;
const int A = (int)61;
const int LOG = 17;
int n, a[N], last_in[N], left_[N], right_[N], sum[N], max_[N][LOG],
    min_[N][LOG], max_pow[N + 1], ans;
void build() {
  for (int i = n - 1; i >= 0; --i) {
    for (int pow = 0; pow < LOG; ++pow) {
      if (pow == 0) {
        min_[i][pow] = sum[i];
        max_[i][pow] = sum[i];
      } else {
        int nxt = i + (1 << pow - 1);
        if (nxt < n) {
          min_[i][pow] = min(min_[i][pow - 1], min_[nxt][pow - 1]);
          max_[i][pow] = max(max_[i][pow - 1], max_[nxt][pow - 1]);
        }
      }
    }
  }
}
pair<int, int> get_val(int l, int r) {
  int pw = max_pow[r - l + 1];
  pair<int, int> res;
  res.first = min(min_[l][pw], min_[r - (1 << pw) + 1][pw]);
  res.second = max(max_[l][pw], max_[r - (1 << pw) + 1][pw]);
  return res;
}
signed main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
  }
  sum[0] = a[0];
  for (int i = 1; i < n; ++i) {
    sum[i] = a[i] + sum[i - 1];
  }
  max_pow[1] = 0;
  for (int i = 2; i <= n; ++i) {
    max_pow[i] = max_pow[i - 1];
    while ((1 << max_pow[i]) <= i) {
      ++max_pow[i];
    }
    --max_pow[i];
  }
  build();
  fill(last_in, last_in + A, -1);
  for (int i = 0; i < n; ++i) {
    int max_ind = -1;
    for (int val = a[i] + 31; val < A; ++val) {
      max_ind = max(max_ind, last_in[val]);
    }
    left_[i] = max_ind + 1;
    last_in[a[i] + 30] = i;
  }
  fill(last_in, last_in + A, n);
  for (int i = n - 1; i >= 0; --i) {
    int max_ind = n;
    for (int val = a[i] + 31; val < A; ++val) {
      max_ind = min(max_ind, last_in[val]);
    }
    right_[i] = max_ind - 1;
    last_in[a[i] + 30] = i;
  }
  ans = -INF;
  for (int i = 0; i < n; ++i) {
    int val1 = get_val(i, right_[i]).second;
    int val2;
    if (left_[i]) {
      val2 = get_val(left_[i] - 1, i - 1).first;
    } else {
      if (left_[i] == i) {
        val2 = 0;
      } else {
        val2 = min(0, get_val(left_[i], i - 1).first);
      }
    }
    ans = max(ans, val1 - val2 - a[i]);
  }
  printf("%d", ans);
  return 0;
}
