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 int maxn = 100000;
template <class T, class U = int>
class RangeMinimumQuery {
 public:
  static const int maxn = ::maxn + 1;
  static const int maxh = 17;
  int n;
  T a[maxn];
  U f[maxn][maxh];
  U select(const U& lhs, const U& rhs) const {
    return a[lhs] <= a[rhs] ? lhs : rhs;
  }
  RangeMinimumQuery(void) { clear(); }
  void clear(void) { n = 0; }
  void resize(const int& n) { this->n = n; }
  void update(const int& i, const bool& rht = false) {
    f[i][0] = i;
    if (!rht) {
      for (int k = 1, b; (b = 1 << k) <= i + 1; k++)
        f[i + 1 - b][k] =
            select(f[i + 1 - b][k - 1], f[i + 1 - (b >> 1)][k - 1]);
    } else {
      for (int k = 1, b; (b = 1 << k) <= n - i; k++)
        f[i][k] = select(f[i][k - 1], f[i + (b >> 1)][k - 1]);
    }
  }
  void push_back(const T& x) {
    a[n] = x;
    update(n++, false);
  }
  void build(void) {
    for (int i = 0; i < n; i++) update(i, false);
  }
  U query(const int& l, const int& r) const {
    int k = 31 - __builtin_clz(r - l);
    return select(f[l][k], f[r - (1 << k)][k]);
  }
};
template <class T, class U = int>
class RangeMaximumQuery {
 public:
  static const int maxn = ::maxn + 1;
  static const int maxh = 17;
  int n;
  T a[maxn];
  U f[maxn][maxh];
  U select(const U& lhs, const U& rhs) const {
    return a[lhs] >= a[rhs] ? lhs : rhs;
  }
  RangeMaximumQuery(void) { clear(); }
  void clear(void) { n = 0; }
  void resize(const int& n) { this->n = n; }
  void update(const int& i, const bool& rht = false) {
    f[i][0] = i;
    if (!rht) {
      for (int k = 1, b; (b = 1 << k) <= i + 1; k++)
        f[i + 1 - b][k] =
            select(f[i + 1 - b][k - 1], f[i + 1 - (b >> 1)][k - 1]);
    } else {
      for (int k = 1, b; (b = 1 << k) <= n - i; k++)
        f[i][k] = select(f[i][k - 1], f[i + (b >> 1)][k - 1]);
    }
  }
  void push_back(const T& x) {
    a[n] = x;
    update(n++, false);
  }
  void build(void) {
    for (int i = 0; i < n; i++) update(i, false);
  }
  U query(const int& l, const int& r) const {
    int k = 31 - __builtin_clz(r - l);
    return select(f[l][k], f[r - (1 << k)][k]);
  }
};
RangeMinimumQuery<int, int> RMQX;
RangeMaximumQuery<int, int> RMQY;
int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  vector<int> b(n + 1, 0);
  partial_sum(a.begin(), a.end(), b.begin() + 1);
  RMQX.resize(n + 1);
  RMQY.resize(n + 1);
  for (int i = 0; i <= n; i++) {
    RMQX.a[i] = b[i];
    RMQY.a[i] = b[i];
  }
  RMQX.build();
  RMQY.build();
  vector<int> vtr(n);
  for (int i = 0; i < n; i++) vtr[i] = i;
  sort(vtr.begin(), vtr.end(),
       [&](const int& lhs, const int& rhs) { return a[lhs] > a[rhs]; });
  set<int> s;
  s.insert(-1);
  s.insert(n);
  int ans = 0;
  for (int i = 0; i < n; i++) {
    const int& u = vtr[i];
    auto itr = s.lower_bound(u);
    int r = *(itr--), l = *itr;
    ans = max(ans,
              b[RMQY.query(u + 1, r + 1)] - b[RMQX.query(l + 1, u + 1)] - a[u]);
    s.insert(u);
  }
  cout << ans << '\n';
  return 0;
}
