#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using P2 = pair<int, P>;
using pll = pair<ll, ll>;
using T = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using vp = vector<P>;
using vt = vector<T>;
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
int main() {
  int n;
  cin >> n;
  vi a(n);
  for (int((i)) = (int)(0); ((i)) < (int)((n)); ++((i))) cin >> a[i];
  int ans = 0;
  queue<P2> q;
  q.push(P2(0, P(1000, 0)));
  vi b(50005, -1);
  b[0] = 1000;
  for (int((i)) = (int)(0); ((i)) < (int)((n)); ++((i))) {
    vi tb = b;
    vi ub = b;
    for (int((j)) = (int)(0); ((j)) < (int)((50004)); ++((j))) {
      chmax(tb[j + 1], tb[j] - a[i]);
    }
    for (int((j)) = (int)((50004)) - 1; ((j)) >= (int)(0); --((j))) {
      if (ub[j + 1] < 0) continue;
      chmax(ub[j], ub[j + 1] + a[i]);
    }
    for (int((i)) = (int)(0); ((i)) < (int)((50005)); ++((i)))
      b[i] = max(tb[i], ub[i]);
  }
  for (int((i)) = (int)(0); ((i)) < (int)((50005)); ++((i))) chmax(ans, b[i]);
  cout << ans << endl;
  return 0;
}
