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>
#pragma comment(linker, "/stack:512000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937_64 gen(time(nullptr));
ll mod = 1e9 + 7;
namespace {
ll mul(ll a, ll b) {
  ll val = a * b - (ll)((ld)a * b / mod) * mod;
  if (val < 0) val += mod;
  if (val >= mod) val -= mod;
  return val;
}
ll poww(ll a, ll b) {
  ll val = 1;
  a %= mod;
  while (b > 0) {
    if (b % 2) val = mul(a, val);
    a = mul(a, a);
    b >>= 1;
  }
  return val % mod;
}
ll inv(ll a) { return poww(a, mod - 2); }
}  // namespace
ll const maxn = 5e5 + 5;
template <typename T>
struct sparse {
  vector<vector<T>> sp;
  vector<T> lg;
  int n, k;
  T f(T& x, T& y) { return min(x, y); }
  sparse(vector<T>& v) {
    n = v.size();
    lg.resize(n + 1);
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    k = lg[n];
    sp.resize(n);
    for (int i = 0; i < n; i++) {
      sp[i].resize(k + 1);
      sp[i][0] = v[i];
    }
    for (int j = 1; j <= k; j++) {
      for (int i = 0; i + (1 << j) <= n; i++) {
        sp[i][j] = f(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  T get(int l, int r) {
    if (r < l) return 0;
    int j = lg[r - l + 1];
    return f(sp[l][j], sp[r - (1 << j) + 1][j]);
  }
};
unordered_map<ll, vector<ll>> g;
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ll n;
  cin >> n;
  vector<ll> a(n);
  for (ll i = 0; i < n; i++) {
    cin >> a[i];
    g[a[i]].push_back(i);
  }
  vector<ll> pref(n), suf(n);
  pref[0] = a[0];
  for (ll i = 1; i < n; i++) pref[i] = pref[i - 1] + a[i];
  suf[n - 1] = a[n - 1];
  for (ll i = n - 2; i >= 0; i--) suf[i] = suf[i + 1] + a[i];
  sparse<ll> suff(suf), preff(pref);
  ll ans = LLONG_MIN;
  set<ll> st;
  st.insert(-1);
  st.insert(n);
  for (ll x = 30; x >= -30; x--) {
    auto& v = g[x];
    for (ll i : v) {
      auto it = st.lower_bound(i);
      auto lt = it;
      lt--;
      ll l = *lt, r = *it;
      ll ans1 = (i + 1 >= n ? 0 : suf[i + 1]) -
                (r < n ? suff.get(i + 1, r) : min(0LL, suff.get(i + 1, r - 1)));
      ans1 +=
          (i ? pref[i - 1] : 0) -
          (l >= 0 ? preff.get(l, i - 1) : min(0LL, preff.get(l + 1, i - 1)));
      ans = max(ans, ans1);
    }
    for (auto i : v) {
      st.insert(i);
    }
  }
  cout << ans << endl;
  return 0;
}
