Limak is an old brown bear. He often goes bowling with his friends. Today he feels really good and tries to beat his own record!

For rolling a ball one gets a score — an integer (maybe negative) number of points. Score for i-th roll is multiplied by i and scores are summed up. So, for k rolls with scores s1, s2, ..., sk, total score is <image>. Total score is 0 if there were no rolls.

Limak made n rolls and got score ai for i-th of them. He wants to maximize his total score and he came up with an interesting idea. He will cancel some rolls, saying that something distracted him or there was a strong wind.

Limak is able to cancel any number of rolls, maybe even all or none of them. Total score is calculated as if there were only non-canceled rolls. Look at the sample tests for clarification. What maximum total score can Limak get?

Input

The first line contains single integer n (1 ≤ n ≤ 105).

The second line contains n space-separated integers a1, a2, ..., an (|ai| ≤ 107) - scores for Limak's rolls.

Output

Print the maximum possible total score after choosing rolls to cancel.

Examples

Input

5
-2 -8 0 5 -3


Output

13


Input

6
-10 20 -30 40 -50 60


Output

400

Note

In first sample Limak should cancel rolls with scores  - 8 and  - 3. Then he is left with three rolls with scores  - 2, 0, 5. Total score is 1·( - 2) + 2·0 + 3·5 = 13.

In second sample Limak should cancel roll with score  - 50. Total score is 1·( - 10) + 2·20 + 3·( - 30) + 4·40 + 5·60 = 400.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, B = 350;
const long long inf = 0x3f3f3f3f3f3f3f3f;
int n, m, a[N], p[N], pos[N], L[N], R[N], size;
long long f[N], ans;
inline bool cmp(int i, int j) { return a[i] < a[j]; }
struct block {
  int l, r, q[B];
  long long k, b;
  inline long long calc(int i) { return f[i] + k * a[i] + b; }
  inline long double slope(int i, int j) {
    if (a[i] == a[j]) return f[i] > f[j] ? -inf : inf;
    return 1.0L * (f[i] - f[j]) / (a[i] - a[j]);
  }
  inline void build(int x) {
    for (int i = L[x]; i <= R[x]; i++) f[i] += k * a[i] + b;
    k = b = r = 0;
    l = 1;
    for (int i = L[x]; i <= R[x]; i++) {
      while (l < r && slope(q[r - 1], q[r]) < slope(q[r], p[i])) r--;
      q[++r] = p[i];
    }
  }
  inline pair<long long, int> query(void) {
    while (l < r && calc(q[l]) <= calc(q[l + 1])) l++;
    return make_pair(calc(q[l]), q[l]);
  }
} t[B];
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  m = sqrt(n);
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) f[i] = a[i];
  for (int i = 1; i <= n; i++) pos[i] = (i - 1) / m + 1;
  for (int i = 1; i <= n; i++) p[i] = i;
  size = pos[n];
  for (int i = 1; i <= size; i++) {
    L[i] = R[i - 1] + 1;
    R[i] = min(n, i * m);
    for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
    sort(p + L[i], p + R[i] + 1, cmp);
  }
  for (int i = 1; i <= size; i++) t[i].build(i);
  while (true) {
    pair<long long, int> res = make_pair(0ll, 0);
    for (int i = 1; i <= size; i++) res = max(res, t[i].query());
    if (!res.first) {
      cout << ans << endl;
      return 0;
    }
    ans += res.first;
    f[res.second] = -inf;
    for (int i = 1; i < pos[res.second]; i++) t[i].b += a[res.second];
    for (int i = L[pos[res.second]]; i < res.second; i++) f[i] += a[res.second];
    for (int i = res.second + 1; i <= R[pos[res.second]]; i++) f[i] += a[i];
    for (int i = pos[res.second] + 1; i <= size; i++) t[i].k++;
    t[pos[res.second]].build(pos[res.second]);
  }
  return 0;
}
