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 \le r$). After that Bob removes a single card $j$ from that segment $(l \le j \le r)$. The score of the game is the total value of the remaining cards on the segment $(a_l + a_{l + 1} + \dots + a_{j - 1} + a_{j + 1} + \dots + 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 \le n \le 10^5$) — the number of cards.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-30 \le a_i \le 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$.

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Amortized analysis

Data structures

Implementation


Solutions:
def max_sum(arr):
	n = len(arr)
	dp = [0 for i in range(n)]
	dp[0] = arr[0]
	for i in range(1, n):
		dp[i] = max(dp[i - 1] + arr[i], arr[i])
	return max(dp)
n = int(input())
l = input().split()
li = [int(i) for i in l]
maxa = 0
for mx in range(-30, 31):
	copy = list(li)
	for i in range(n):
		if copy[i] > mx:
			copy[i] = -1000000000000
	maxa = max(max_sum(copy) - mx, maxa)
print(maxa)


n = int(input())
s = list(map(int, input().split()))
ans = 0
inf = -99999999999999999
for mx in range(31):
	c = b = 0
	for i in s:
		if i > mx:
			i = inf
		c += i
		b = min(b, c)
		ans = max(ans, c - b - mx)
print(ans)


import sys
import math

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
t = II()
a = LI()
ans = []
for j in range(30, 0, -1):
	s = 0
	answer = 0
	m = 0
	for i in range(t):
		if a[i] > j:
			s = 0
			m = 0
			continue
		s += a[i]
		if s - m > answer:
			answer = s - m
		if m > s:
			m = s
	ans.append(answer)
m = 0
for i in range(30):
	m = max(m, ans[i] - (30 - i))
print(m)


from itertools import accumulate
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

class SparseTableMax:

	def __init__(self, aa):
		w = len(aa)
		h = w.bit_length()
		table = [aa] + [[-1] * w for _ in range(h - 1)]
		tablei1 = table[0]
		for i in range(1, h):
			tablei = table[i]
			for j in range(w - (1 << i) + 1):
				rj = j + (1 << i - 1)
				tablei[j] = max(tablei1[j], tablei1[rj])
			tablei1 = tablei
		self.table = table

	def max(self, l, r):
		i = (r - l).bit_length() - 1
		tablei = self.table[i]
		Lmax = tablei[l]
		Rmax = tablei[r - (1 << i)]
		if Lmax > Rmax:
			Rmax = Lmax
		return Rmax

class SparseTableMin:

	def __init__(self, aa):
		w = len(aa)
		h = w.bit_length()
		table = [aa] + [[-1] * w for _ in range(h - 1)]
		tablei1 = table[0]
		for i in range(1, h):
			tablei = table[i]
			for j in range(w - (1 << i) + 1):
				rj = j + (1 << i - 1)
				tablei[j] = min(tablei1[j], tablei1[rj])
			tablei1 = tablei
		self.table = table

	def min(self, l, r):
		i = (r - l).bit_length() - 1
		tablei = self.table[i]
		Lmin = tablei[l]
		Rmin = tablei[r - (1 << i)]
		if Lmin < Rmin:
			Rmin = Lmin
		return Rmin

def main():
	inf = 10 ** 16
	n = II()
	aa = LI()
	ll = [0] * n
	stack = []
	for (i, a) in enumerate(aa):
		while stack and stack[-1][-1] <= a:
			stack.pop()
		if stack:
			ll[i] = stack[-1][0] + 1
		stack.append((i, a))
	rr = [n] * n
	stack = []
	for i in range(n - 1, -1, -1):
		a = aa[i]
		while stack and stack[-1][-1] <= a:
			stack.pop()
		if stack:
			rr[i] = stack[-1][0]
		stack.append((i, a))
	cs = [0] + [s for s in accumulate(aa)]
	mn = SparseTableMin(cs)
	mx = SparseTableMax(cs)
	ans = -inf
	for i in range(n):
		(l, r) = (ll[i], rr[i])
		cur = mx.max(i + 1, r + 1) - mn.min(l, i + 1) - aa[i]
		if cur > ans:
			ans = cur
	print(ans)
main()


n = int(input())
arr = list(map(int, input().split()))
ans = 0
for i in range(31):
	s = 0
	for j in arr:
		if j <= i:
			s = max(0, s + j)
		else:
			s = 0
		ans = max(s - i, ans)
print(ans)


from collections import deque
import sys
input = sys.stdin.readline

class Ruiseki_lr:

	def __init__(self, array, op, e):
		self.op = op
		self.e = e
		n = len(array)
		self.left = [e] * (n + 1)
		self.right = [e] * (n + 1)
		for i in range(n):
			self.left[i + 1] = self.op(self.left[i], array[i])
		for i in reversed(range(n)):
			self.right[i] = self.op(self.right[i + 1], array[i])

	def get_left(self, p):
		return self.left[p]

	def get_right(self, p):
		return self.right[p]

	def fold(self, p):
		return self.op(self.left[p], self.right[p + 1])

class SegmentTree:

	def __init__(self, n, op, e):
		self.n = n
		self.op = op
		self.e = e
		self.size = 2 ** (n - 1).bit_length()
		self.node = [self.e] * (2 * self.size)

	def build(self, array):
		for i in range(self.n):
			self.node[self.size + i] = array[i]
		for i in range(self.size - 1, 0, -1):
			self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

	def update(self, i, val):
		i += self.size
		self.node[i] = val
		while i > 1:
			i >>= 1
			self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

	def get_val(self, l, r):
		(l, r) = (l + self.size, r + self.size)
		(res_l, res_r) = (self.e, self.e)
		while l < r:
			if l & 1:
				res_l = self.op(res_l, self.node[l])
				l += 1
			if r & 1:
				r -= 1
				res_r = self.op(self.node[r], res_r)
			(l, r) = (l >> 1, r >> 1)
		return self.op(res_l, res_r)
n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 5
right = [n] * n
q = deque([])
for i in range(n)[::-1]:
	while True:
		if not q:
			q.append((a[i], i))
			break
		if q[-1][0] < a[i]:
			q.pop()
			continue
		if q[-1][0] == a[i]:
			q.pop()
			continue
		if q[-1][0] > a[i]:
			right[i] = q[-1][1]
			q.append((a[i], i))
			break
left = [0] * n
q = deque([])
for i in range(n):
	while True:
		if not q:
			q.append((a[i], i))
			break
		if q[-1][0] < a[i]:
			q.pop()
			continue
		if q[-1][0] == a[i]:
			q.pop()
			continue
		if q[-1][0] > a[i]:
			left[i] = q[-1][1] + 1
			q.append((a[i], i))
			break
ru = Ruiseki_lr(a, lambda x, y: x + y, 0)
st_l = SegmentTree(n + 1, max, -10 ** 18)
st_r = SegmentTree(n + 1, max, -10 ** 18)
st_l.build(ru.left)
st_r.build(ru.right)
ans = 0
for i in range(n):
	(l, r) = (left[i], right[i])
	tmp = 0
	tmp += max(st_l.get_val(i + 1, r + 1) - ru.left[i + 1], 0)
	tmp += max(st_r.get_val(l, i) - ru.get_right(i), 0)
	ans = max(ans, tmp)
print(ans)


import os
import sys
from math import *
from collections import *
from heapq import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz/'
M = 1000000007
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
n = Int()
a = array()
ans = 0
for mx in range(-31, 32):
	here = 0
	ma = 0
	for i in a:
		if i > mx:
			ans = max(here - ma, ans)
			here = 0
			ma = 0
		else:
			here += i
			ma = max(ma, i)
			ans = max(here - ma, ans)
			if here < 0:
				here = 0
				ma = 0
	ans = max(here - ma, ans)
print(ans)


import sys
import os.path
INF = int(1000000000.0)
if os.path.isfile('in.txt'):
	sys.stdin = open('in.txt', 'r', encoding='utf-8')
n = int(input())
arr = list(map(int, input().split()))
ans = 0
for _max in range(0, 31):
	_sum = 0
	max_sum = -INF
	for num in arr:
		val = num if num <= _max else -INF
		_sum += val
		max_sum = max(max_sum, _sum)
		_sum = max(_sum, 0)
	ans = max(ans, max_sum - _max)
print(ans)


from sys import stdin
input = lambda : stdin.readline().strip()
char = [chr(i) for i in range(97, 123)]
CHAR = [chr(i) for i in range(65, 91)]
mp = lambda : list(map(int, input().split()))
INT = lambda : int(input())
rn = lambda : range(INT())
mod = 10000000007
from math import ceil, sqrt, factorial, gcd
n = INT()
l = mp()
h = set()
for i in l:
	if i >= 0 and i not in h:
		h.add(i)
mx_sm = 0
for i in h:
	sm = 0
	for j in range(n):
		if l[j] > i:
			mx_sm = max(mx_sm, sm - i)
			sm = 0
		elif sm + l[j] < 0:
			mx_sm = max(sm - i, 0, mx_sm)
			sm = 0
		else:
			sm += l[j]
			sm = max(0, sm)
			mx_sm = max(mx_sm, sm - i, 0)
	mx_sm = max(mx_sm, sm - i, 0)
print(mx_sm)


def answer(n, A):
	ans = 0
	for i in range(1, 31):
		s = 0
		for j in range(n):
			if A[j] > i:
				s = 0
			else:
				s += A[j]
				s = max(s, 0)
				ans = max(ans, s - i)
	return ans
n = int(input())
A = list(map(int, input().split()))
print(answer(n, A))


INF = 1000000000.0
n = int(input())
a = list(map(int, input().split()))
ans = 0
for max_ in range(0, 31):
	curr = 0
	best = 0
	for i in range(n):
		val = -INF
		if a[i] <= max_:
			val = a[i]
		curr += val
		best = min(best, curr)
		ans = max(ans, curr - best - max_)
print(int(ans))


from sys import stdin
input = stdin.buffer.readline
n = int(input())
(*a,) = map(int, input().split())
ans = 0
for i in range(31):
	s = 0
	for j in a:
		if j <= i:
			s = max(0, s + j)
		else:
			s = 0
		ans = max(ans, s - i)
print(ans)


from sys import stdin
input = stdin.readline

def main():
	n = int(input())
	l = [int(i) for i in input().split(' ')]
	maxi = 0
	for i in range(1, 31):
		if i in l:
			score = 0
			for j in l:
				if j <= i:
					score += j
					maxi = max(maxi, score - i)
					score = max(score, 0)
				else:
					score = 0
	print(maxi)
main()


def run(arr):
	ans = 0
	for mx in range(0, 31):
		acc = 0
		for x in arr:
			if x > mx:
				acc = 0
				continue
			acc += x
			acc = max(acc, 0)
			ans = max(ans, acc - mx)
	return ans

def main():
	from sys import stdin
	import os
	if os.path.exists('tmp.in'):
		stdin = open('tmp.in')
	n = int(stdin.readline())
	arr = [int(x) for x in stdin.readline().split()]
	ans = run(arr)
	print(ans)
main()


n = int(input())
a = list(map(int, input().split()))
ans = 0
for m in range(1, 31):
	now = 0
	f = 0
	for v in a:
		if v > m or now + v <= 0:
			now = 0
			f = 0
		else:
			now += v
			if v == m:
				f = 1
			if f:
				ans = max(ans, now - m)
print(ans)


def maxSubArraySum(a, size):
	j = 30
	ans = 0
	while j >= 1:
		max1 = 0
		max_so_far = 0
		max_ending_here = 0
		for i in range(size):
			if a[i] > j:
				max_ending_here = 0
			elif a[i] <= j:
				max_ending_here = max_ending_here + a[i]
				max1 = max(max1, a[i])
			if max_ending_here < 0:
				max_ending_here = 0
			elif max_so_far < max_ending_here:
				max_so_far = max_ending_here
		j -= 1
		ans = max(ans, max_so_far - max1)
	return ans
n = int(input())
num1 = list(map(int, input().split()))
print(maxSubArraySum(num1, n))


from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
if os.path.exists('in.txt'):
	sys.stdin = open('in.txt', 'r')
if os.path.exists('out.txt'):
	sys.stdout = open('out.txt', 'w')

def input():
	return sys.stdin.readline()

def mapi(arg=0):
	return map(int if arg == 0 else str, input().split())
n = int(input())
a = list(mapi())
res = 0
mn = min(a) - 100000
for i in range(31):
	cur = a[0] if a[0] <= i else mn
	mxsm = a[0] if a[0] <= i else mn
	for j in range(1, n):
		if a[j] <= i:
			cur = max(a[j], cur + a[j])
			mxsm = max(mxsm, cur)
		else:
			cur = max(mn, cur + mn)
			mxsm = max(mxsm, cur)
	res = max(res, mxsm - i)
print(res)


def main():
	(N, A, cnt) = (int(input()), list(map(int, input().split())), 0)
	for a in A:
		if a > 0:
			cnt += 1
	if cnt <= 1:
		print(0)
		return
	M = [0] * 31
	for i in range(30, 0, -1):
		(m, now, diff) = (0, 0, 0)
		for a in A:
			if a > i:
				(m, now) = (0, 0)
				continue
			now += a
			if diff < now - m:
				diff = now - m
			if now < m:
				m = now
		M[i] = diff
	print(max([M[i] - i for i in range(31)]))
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	n = N()
	arr = RLL()
	res = 0
	for i in range(1, 31):
		sm = 0
		ma = 0
		for j in arr:
			now = j if j <= i else -INF
			sm += now
			ma = max(ma, now)
			res = max(sm - ma, res)
			if sm < 0:
				ma = 0
				sm = 0
	print(res)
main()


n = int(input())
l = list(map(int, input().split()))
curr = 0
best = 0
prevs = [0] * 31
for v in l:
	curr += v
	if v >= 0:
		for i in range(0, v):
			prevs[i] = curr
		for i in range(v, 31):
			best = max(curr - prevs[i] - i, best)
	else:
		for i in range(31):
			prevs[i] = min(prevs[i], curr)
print(best)


n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(30, 0, -1):
	mxsum = 0
	for j in range(0, n):
		if a[j] > i:
			mxsum = 0
			continue
		mxsum += a[j]
		mxsum = max(0, mxsum)
		ans = max(ans, mxsum - i)
print(ans)


n = int(input())
a = list(map(int, input().split()))
if max(a) <= 0:
	exit(print(0))
ans = [0] * 31
for i in range(1, 31):
	mi = su = 0
	for x in a:
		if x > i:
			mi = anss = 0
			continue
		su += x
		ans[i] = max(ans[i], su - mi)
		mi = min(mi, su)
print(max((ans[i] - i for i in range(31))))


x = int(input())
a = list(map(int, input().split()))
res = 0
for i in range(32):
	(s, max1, s1) = (0, 0, 0)
	for j in a:
		if j <= i:
			s += j
			max1 = max(max1, s - s1)
			s1 = min(s1, s)
		else:
			s1 = 0
			s = 0
	res = max(res, max1 - i)
print(res)


import collections
import time
import os
import sys
import bisect
import heapq
from typing import List
INF = 10 ** 7

class SegmentTree:

	def __init__(self, size, useMax):
		n = size * 4 + 1
		v = -INF if useMax else INF
		self.data = [v for _ in range(n)]
		self.size = size
		self.n = n
		self.useMax = useMax
		self.lazy = [False for _ in range(n)]

	def push(self, index):
		pass

	def build(self):
		pass

	def update(self, index, val):
		self.update_impl(1, 0, self.size - 1, index, index, val)

	def query(self, start, end):
		return self.query_impl(1, 0, self.size - 1, start, end)

	def update_impl(self, index, nodel, noder, targetl, targetr, val):
		if nodel > noder or targetl > targetr:
			return -INF if self.useMax else INF
		self.push(index)
		if nodel == targetl and noder == targetr:
			self.data[index] = max(self.data[index], val) if self.useMax else min(self.data[index], val)
			return self.data[index]
		m = (nodel + noder) // 2
		a = self.update_impl(index * 2, nodel, min(m, noder), targetl, min(m, targetr), val)
		b = self.update_impl(index * 2 + 1, max(nodel, m + 1), noder, max(targetl, m + 1), targetr, val)
		c = max(a, b) if self.useMax else min(a, b)
		self.data[index] = max(self.data[index], c) if self.useMax else min(self.data[index], c)
		return c

	def query_impl(self, index, nodel, noder, targetl, targetr):
		if nodel > noder or targetl > targetr:
			return -INF if self.useMax else INF
		self.push(index)
		if nodel == targetl and noder == targetr:
			return self.data[index]
		m = (nodel + noder) // 2
		a = self.query_impl(index * 2, nodel, min(m, noder), targetl, min(m, targetr))
		b = self.query_impl(index * 2 + 1, max(m + 1, nodel), noder, max(m + 1, targetl), targetr)
		c = max(a, b) if self.useMax else min(a, b)
		return c

def solve(N, A):
	presum = [0]
	for v in A:
		presum.append(presum[-1] + v)
	left = []
	q = []
	st = SegmentTree(N, useMax=False)
	for (i, v) in enumerate(A):
		while q and q[-1][0] <= v:
			q.pop()
		j = q[-1][1] + 1 if q else 0
		left.append(max(presum[i] - st.query(j, i - 1), 0))
		st.update(i, presum[i])
		q.append((v, i))
	right = []
	q = []
	st = SegmentTree(N, useMax=True)
	for i in range(N - 1, -1, -1):
		v = A[i]
		while q and q[-1][0] <= v:
			q.pop()
		j = q[-1][1] - 1 if q else N - 1
		right.append(max(0, st.query(i + 1, j) - presum[i + 1]))
		st.update(i, presum[i + 1])
		q.append((v, i))
	right = right[::-1]
	return max([a + b for (a, b) in zip(left, right)])
N = int(input())
A = [int(x) for x in input().split()]
print(solve(N, A))


def solve_excluding(a, u):
	best_sum = 0
	current_sum = 0
	seen = False
	seen_at_some_point = False
	for el in a:
		if el > u or current_sum + el < 0:
			current_sum = 0
			seen = False
		else:
			current_sum += el
			if el == u:
				seen = True
			if current_sum >= best_sum and seen:
				best_sum = current_sum
				seen_at_some_point = True
	return (seen_at_some_point, best_sum)
n = int(input())
a = [int(x) for x in input().split()]
best = 0
for u in range(-30, 31):
	(seen, total) = solve_excluding(a, u)
	if seen:
		total -= u
		if total > best:
			best = total
print(best)


import sys
input = sys.stdin.readline
n = int(input())
l = input().split()
li = [int(i) for i in l]
maxa = -10 ** 9
for i in range(-32, 32):
	l = []
	for j in range(n):
		if li[j] <= i:
			l.append(li[j])
		else:
			if l == []:
				continue
			dp = [0 for ok in range(len(l))]
			dp[0] = l[0]
			for k in range(1, len(l)):
				dp[k] = max(dp[k - 1] + l[k], l[k])
			z = max(dp)
			maxa = max(z - i, maxa)
			l = []
	if l != []:
		dp = [0 for ok in range(len(l))]
		dp[0] = l[0]
		for k in range(1, len(l)):
			dp[k] = max(dp[k - 1] + l[k], l[k])
		z = max(dp)
		maxa = max(z - i, maxa)
		l = []
print(maxa)


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	temp = list(map(int, input().split(' ')))
	meraans = 0
	for y in range(-30, 31):
		a = list(temp)
		csseg = 0
		maxsofar = -100
		for x in range(n):
			if a[x] > y:
				a[x] = -100000
			csseg = csseg + a[x]
			maxsofar = max(maxsofar, a[x])
			meraans = max(meraans, csseg - maxsofar)
			if csseg <= 0:
				csseg = 0
				maxsofar = -100
	print(meraans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os
import sys
if os.path.exists('/mnt/c/Users/Square/square/codeforces'):
	f = iter(open('D.txt').readlines())

	def input():
		return next(f)
else:
	input = lambda : sys.stdin.readline().strip()
fprint = lambda *args: print(*args, flush=True)
n = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(1, 31):
	res = 0
	for j in A:
		res += j
		if j > i:
			res = 0
		res = max(res, 0)
		ans = max(ans, res - i)
print(ans)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	n = inp()
	l = li()
	ans = 0
	cur = [-INF] * n
	for maxi in range(-30, 31):
		dp = list(cur)
		val = -INF
		if l[0] <= maxi:
			dp[0] = l[0]
		for i in range(1, n):
			if l[i] <= maxi:
				dp[i] = max(l[i], l[i] + dp[i - 1])
			val = max(val, dp[i])
		ans = max(ans, val - maxi)
	pr(ans)
for _ in range(1):
	solve()


n = int(input())
A = list(map(int, input().split()))
for a in A:
	if a > 0:
		break
else:
	print(0)
	exit()
if n == 1:
	print(0)
	exit()
ans = -1
INF = 10 ** 18
for M in range(1, 31):
	dp = [0] * n
	if A[0] > M:
		dp[0] = -INF
	else:
		dp[0] = A[0]
	for i in range(1, n):
		if A[i] > M:
			a = -INF
		else:
			a = A[i]
		dp[i] = max(dp[i - 1] + a, a)
	ans = max(ans, max(dp) - M)
print(ans)


from bisect import bisect_left as lower_bound, bisect_right as upper_bound
from sys import stdin, stdout
from collections import defaultdict
N = 10 ** 5 + 7
minn = [0 for _ in range(2 * N)]
maxx = [0 for _ in range(2 * N)]

def build(p, n):
	for i in range(n):
		maxx[n + i] = p[i]
		minn[n + i] = p[i]
	for i in range(n - 1, 0, -1):
		maxx[i] = max(maxx[i << 1], maxx[i << 1 | 1])
		minn[i] = min(minn[i << 1], minn[i << 1 | 1])

def query(l, r, n):
	l += n
	r += n
	(retminn, retmaxx) = (float('inf'), -float('inf'))
	while l < r:
		if l & 1:
			retminn = min(retminn, minn[l])
			retmaxx = max(retmaxx, maxx[l])
			l += 1
		if r & 1:
			r -= 1
			retminn = min(retminn, minn[r])
			retmaxx = max(retmaxx, maxx[r])
		l >>= 1
		r >>= 1
	return (retminn, retmaxx)

def main():
	n = int(input())
	a = list(map(int, input().strip().split()))
	left = [-1] * n
	right = [n] * n
	p = [a[i] for i in range(n)]
	for i in range(1, n):
		p[i] += p[i - 1]
	build(p, n)
	st = [0]
	for i in range(1, n):
		while st and a[st[-1]] <= a[i]:
			st.pop()
		if st:
			left[i] = st[-1]
		st.append(i)
	st = [n - 1]
	for i in range(n - 2, -1, -1):
		while st and a[st[-1]] < a[i]:
			st.pop()
		if st:
			right[i] = st[-1]
		st.append(i)
	if max(a) <= 0:
		print(0)
		return None
	ret = -float('inf')
	for i in range(n):
		(l, r) = (left[i], right[i])
		(_, rmaxx) = query(i, r, n)
		(lminn, _) = query(max(0, l), i, n)
		if l < 0:
			lminn = min(lminn, 0)
		s = rmaxx - lminn
		ret = max(ret, s - a[i])
	print(ret)
main()


import sys
input = sys.stdin.buffer.readline

def print(val):
	sys.stdout.write(str(val) + '\n')
i_kart = int(input())
lista = [int(x) for x in input().split()]
wynik = 0
for i in range(31):
	if lista[0] > i:
		max_local = max_total = 0
	else:
		max_local = max_total = lista[0]
	for x in lista[1:]:
		if x > i:
			continue
		max_local = max(x, max_local + x)
		max_total = max(max_total, max_local)
	wynik = max(wynik, max_total - i)
print(wynik)


import sys
input = sys.stdin.buffer.readline
n = int(input())
ls = list(map(int, input().split()))
m = max(ls)

def get_max(ls):
	ma = [[0] * n for _ in range(m + 1)]
	for i in range(1, m + 1):
		mx = 0
		for (j, u) in enumerate(ls):
			mx += u
			if mx <= 0 or u > i:
				mx = 0
			ma[i][j] = mx
	return ma
(ml, mr) = (get_max(ls), get_max(list(reversed(ls))))
mr = [list(reversed(u)) for u in mr]
mx = 0
for (i, u) in enumerate(ls):
	if u <= 0:
		continue
	lv = ml[u][i - 1] if i > 0 else 0
	rv = mr[u][i + 1] if i < n - 1 else 0
	mx = max(mx, lv + rv)
print(mx)


from __future__ import division, print_function
import itertools
import sys
import os
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	input = raw_input
	range = xrange
	filter = itertools.ifilter
	map = itertools.imap
	zip = itertools.izip

def is_it_local():
	script_dir = str(os.getcwd()).split('/')
	username = 'dipta007'
	return username in script_dir

def READ(fileName):
	if is_it_local():
		sys.stdin = open(f'./{fileName}', 'r')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if not is_it_local():
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	input = lambda : sys.stdin.readline().rstrip('\r\n')

def input1(type=int):
	return type(input())

def input2(type=int):
	[a, b] = list(map(type, input().split()))
	return (a, b)

def input3(type=int):
	[a, b, c] = list(map(type, input().split()))
	return (a, b, c)

def input_array(type=int):
	return list(map(type, input().split()))

def input_string():
	s = input()
	return list(s)

def main():
	n = input1()
	ar = input_array()
	res = 0
	for mx in range(-30, 31):
		cum = 0
		for v in ar:
			cum += v
			if v > mx:
				cum = -1000000000.0
			res = max(res, cum - mx)
			if cum < 0:
				cum = 0
	print(res)
	pass
main()


n = int(input())
arr = list(map(int, input().split()))
ans = 0
for i in range(1, 31):
	res = 0
	for j in arr:
		res += j
		if j > i:
			res = 0
		res = max(res, 0)
		ans = max(ans, res - i)
print(ans)


from fractions import Fraction
import bisect
import os
from collections import Counter
import bisect
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce, cmp_to_key
from collections import deque
import threading
from itertools import combinations
from io import BytesIO, IOBase
from itertools import accumulate

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())
mod = int(1000000000.0) + 7

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
t = 1
for _ in range(t):
	n = iinput()
	a = rlinput()
	ans = 0
	for i in range(1, 31):
		s = 0
		for j in a:
			if j <= i:
				s = max(0, j + s)
			else:
				s = 0
			ans = max(ans, s - i)
	print(ans)


from heapq import *
from collections import *
import os
import sys
from io import BytesIO, IOBase
import math
ins = lambda : [int(x) for x in input()]
inp = lambda : int(input())
inps = lambda : [int(x) for x in input().split()]
from fractions import Fraction as F

def main():
	n = inp()
	a = inps()
	ans = 0
	cs = 0
	for v in range(30, 0, -1):
		re = 0
		cs = 0
		while re < n:
			if a[re] > v:
				cs = 0
				re += 1
				continue
			cs += a[re]
			cs = max(cs, 0)
			ans = max(ans, cs - v)
			re += 1
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
cards = [int(x) for x in input().split()]
possibleVals = set()
for x in cards:
	possibleVals.add(x)
ans = -999999999
for v in possibleVals:
	segmentHasV = True if v == cards[0] else False
	maxContiguousSum = cards[0]
	if maxContiguousSum > v:
		maxContiguousSum = -9999999999
	if segmentHasV:
		ans = max(ans, maxContiguousSum - v)
	for i in range(1, len(cards)):
		e = cards[i]
		if e == v:
			segmentHasV = True
		if e > v:
			e = -9999999999
		maxContiguousSum = max(maxContiguousSum + e, e)
		if segmentHasV == True:
			ans = max(ans, maxContiguousSum - v)
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def S():
	return input().strip()

def print_list(l):
	print(' '.join(map(str, l)))
n = N()
a = RLL()
M = 10000000
dic = [M] * 61
s = 0
last = 100
res = -float('inf')
for v in a:
	v += 30
	t = s
	if v > last:
		for i in range(last, v):
			t = min(t, dic[i])
			dic[i] = M
	dic[v] = min(dic[v], t)
	s += v - 30
	for m in range(v, 61):
		res = max(res, s - dic[m] - m + 30)
	last = v
print(res)


import sys
input = sys.stdin.buffer.readline

def I():
	return list(map(int, input().split()))

def sieve(n):
	a = [1] * n
	for i in range(2, n):
		if a[i]:
			for j in range(i * i, n, i):
				a[j] = 0
	return a
n = int(input())
arr = I()
ans = 0
for i in range(-32, 33):
	maxs = -33
	f = 0
	currmax = -33
	for j in range(n):
		if arr[j] == i:
			f = 1
		if arr[j] > i:
			currmax = -33
			continue
		currmax = max(arr[j] + currmax, arr[j])
		maxs = max(currmax, maxs)
	if f:
		ans = max(maxs - i, ans)
print(ans)


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	List = list(map(int, input().split()))
	max_val = 0
	for maxi in range(1, 31):
		curr = 0
		for val in List:
			if val > maxi:
				curr = 0
			else:
				curr = max(val, curr + val)
				max_val = max(max_val, curr - maxi)
	print(max_val)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
import math as mt
input = sys.stdin.buffer.readline
t = 1
for __ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = [-10 ** 9] * (n + 1)
	ans = 0
	for i in range(31):
		for j in range(n):
			if l[j] <= i:
				a[j] = l[j]
		curr = 0
		maxi = 0
		for j in range(n):
			curr += a[j]
			maxi = max(curr, maxi)
			if curr < 0:
				curr = 0
		ans = max(ans, maxi - i)
	print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
l = list(map(int, input().split()))
d = set(l)
ans = 0
tot = 0
for j in range(31):
	if j not in d:
		continue
	tot = -999999999999999999999
	cur = 0
	for i in range(n):
		if l[i] > j:
			cur = 0
			continue
		else:
			cur += l[i]
			if cur < 0:
				cur = 0
			tot = max(tot, cur)
	ans = max(tot - j, ans)
print(ans)


from sys import stdin, stdout

def yet_another_yet_another_task(a):
	res = 0
	for i in range(1, 31):
		mxr = 0
		mnr = 0
		for j in a:
			if j > i:
				mxr = 0
				mnr = 0
			else:
				mxr += j
				mnr = min(mxr, mnr)
				res = max(res, mxr - mnr - i)
	return res
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
stdout.write(str(yet_another_yet_another_task(a)) + '\n')


import math, sys
from collections import defaultdict, Counter, deque
INF = float('inf')
MOD = int(1000000000.0) + 7
MAX = int(200000.0) + 1

def solve():
	n = int(input())
	arr = array()
	ans = 0
	for maxi in range(1, 31):
		curr = 0
		best = 0
		for i in range(n):
			if arr[i] <= maxi:
				curr = max(curr + arr[i], arr[i])
				best = max(best, curr)
		ans = max(ans, best - maxi)
	print(ans)

def main():
	t = 1
	for _ in range(t):
		solve()

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def input():
	return sys.stdin.readline().rstrip('\n').strip()

def print(*args, sep=' ', end='\n'):
	first = True
	for arg in args:
		if not first:
			sys.stdout.write(sep)
		sys.stdout.write(str(arg))
		first = False
	sys.stdout.write(end)

def vars():
	return map(int, input().split())

def array():
	return list(map(int, input().split()))
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def write(*args, end='\n'):
	for x in args[:-1]:
		sys.stdout.write(str(x) + ' ')
	sys.stdout.write(str(args[-1]))
	sys.stdout.write(end)

def r_array():
	return [int(x) for x in input().split()]

def r_int():
	return int(input())
n = int(input())
arr = list(map(int, input().split()))
ans = 0
for i in range(1, 31):
	mu_now = 0
	fin = 0
	for j in range(n):
		if arr[j] > i:
			fin = 0
			mu_now = 0
			continue
		mu_now += arr[j]
		if arr[j] == i:
			fin = 1
		mu_now = max(mu_now, 0)
		if fin:
			ans = max(ans, mu_now - i)
print(ans)


import sys
import math
from collections import defaultdict, deque
import heapq
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
a = set()
for i in range(n):
	a.add(arr[i])
ans = 0
for j in a:
	b = [i for i in arr]
	for i in range(n):
		if b[i] > j:
			b[i] = -float('inf')
	s = 0
	nax = -35
	for i in range(n):
		if s + b[i] >= 0:
			s += b[i]
			nax = max(nax, b[i])
			ans = max(ans, s - nax)
		else:
			s = 0
			nax = -35
print(ans)


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 10
MOD = 10 ** 9 + 7
N = INT()
A = LIST()
nums = sorted(set(A), reverse=1)
ans = -INF
for num in nums:
	dp0 = [-INF] * (N + 1)
	dp1 = [-INF] * (N + 1)
	for i in range(N):
		if A[i] < num:
			dp0[i + 1] = max(dp0[i + 1], dp0[i] + A[i], A[i])
			dp1[i + 1] = max(dp1[i + 1], dp1[i] + A[i], A[i])
		elif A[i] == num:
			dp1[i + 1] = max(dp1[i + 1], dp0[i] + A[i], A[i])
			dp1[i + 1] = max(dp1[i + 1], dp1[i] + A[i], A[i])
	ans = max(ans, max(dp1) - num)
print(ans)


import sys
from collections import deque

class st:

	def __init__(self, arr):
		self.n = len(arr)
		self.t = [0 for i in range(2 * self.n)]
		for i in range(self.n):
			self.t[self.n + i] = arr[i]
		self.build_tree_min(arr)

	def build_tree_min(self, arr):
		for i in range(self.n - 1, 0, -1):
			self.t[i] = min(self.t[2 * i], self.t[2 * i + 1])

	def query(self, l, r):
		if l >= r:
			return 0
		res = sys.maxsize
		l += self.n
		r += self.n
		while l < r:
			if l & 1 == 1:
				res = min(res, self.t[l])
				l += 1
			if r & 1 == 1:
				r -= 1
				res = min(res, self.t[r])
			l = l // 2
			r = r // 2
		return res
n = int(input())
p = list(map(int, input().split()))
(prev_max, next_max) = ([0 for i in range(n)], [0 for j in range(n)])
q = deque([])
q.append(0)
for i in range(1, n):
	while len(q) > 0:
		if p[q[-1]] < p[i]:
			next_max[q[-1]] = i
			q.pop()
		else:
			break
	q.append(i)
for i in q:
	next_max[i] = n
q = deque([])
q.append(n - 1)
for i in range(n - 2, -1, -1):
	while len(q) > 0:
		if p[q[-1]] < p[i]:
			prev_max[q[-1]] = i
			q.pop()
		else:
			break
	q.append(i)
for i in q:
	prev_max[i] = -1
pre = [0] + p
suff = p + [0]
for i in range(1, len(pre)):
	pre[i] += pre[i - 1]
for i in range(len(suff) - 2, -1, -1):
	suff[i] += suff[i + 1]
ans = 0
s1 = st(pre)
s2 = st(suff)
for i in range(n):
	ans = max(ans, -p[i] + pre[n] - s2.query(i + 1, next_max[i] + 1) - s1.query(prev_max[i] + 1, i + 1))
print(ans)


def kandane(a):
	best = -10 ** 10
	current = 0
	for i in range(len(a)):
		if current >= 0:
			current += a[i]
		else:
			current = a[i]
		best = max(current, best)
	return best
n = int(input())
arr = [int(i) for i in input().split()]
ans = 0
for pot_max in range(1, 31):
	barr = [a if a <= pot_max else -10000000 for a in arr]
	ans = max(ans, kandane(barr) - pot_max)
print(ans)


def inp():
	return int(input())
import math

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
import bisect
N = inp()
big = 0
li = inlt()
for j in range(31):
	val = 0
	for item in li:
		if item <= j:
			val = max(0, val + item)
		else:
			val = 0
		big = max(big, val - j)
if big < 0:
	print(0)
else:
	print(big)


n = int(input())
ar = list(map(int, input().split()))
ans = 0
for i in range(0, 31):
	(a, b) = (0, 0)
	for e in ar:
		e = e if e <= i else -float('inf')
		a = max(e, a + e)
		b = max(a, b)
	ans = max(ans, b - i)
print(ans)


import sys
input = sys.stdin.readline
from collections import defaultdict

def kadane(hi, lo, sub_max):
	max_so_far = 0
	max_ending_here = 0
	for i in range(hi, lo):
		max_ending_here = max_ending_here + l[i]
		if max_ending_here < 0:
			max_ending_here = 0
		elif max_so_far < max_ending_here:
			max_so_far = max_ending_here
	return max_so_far - sub_max
n = int(input())
l = [int(i) for i in input().split()]
maxl = max(l)
ind = defaultdict(list)
stack = []
ind_arr = [0] * 31
for i in range(len(l)):
	if l[i] >= 0:
		ind_arr[l[i]] = i
		while len(stack) > 0 and stack[-1] < l[i]:
			temp = stack.pop()
			ind[temp][-1].append(i)
		if len(stack) == 0:
			ind[l[i]].append([0])
		elif stack[-1] != l[i]:
			ind[l[i]].append([ind_arr[stack[-1]] + 1])
		stack.append(l[i])
ans = [0]
for i in ind:
	for j in ind[i]:
		if len(j) == 1:
			ans.append(kadane(j[0], n, i))
		else:
			ans.append(kadane(j[0], j[1], i))
sys.stdout.write(str(max(ans)) + '\n')


import sys, math, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
from decimal import Decimal
from fractions import Fraction

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
INF = 10 ** 20
mod = 10 ** 9 + 7
n = int(data())
a = mdata()
ans = 0
for i in range(1, 31):
	m = 0
	s = 0
	for j in range(n):
		if m < a[j]:
			m = a[j]
		s += a[j]
		if m == i:
			ans = max(ans, s - m)
		elif m > i:
			m = 0
			s = 0
		if s < 0:
			s = 0
			m = 0
out(ans)


n = int(input())
a = [int(x) for x in input().split()]
if all((x <= 0 for x in a)):
	print(0)
	import sys
	sys.exit(0)
pvs = list(reversed(sorted([x for x in set(a) if x > 0])))
obest = 0
for v in pvs:
	cv = 0
	poss = False
	for x in a:
		if x == v:
			poss = True
			cv += x
			obest = max(obest, cv - v)
		elif x < v:
			cv += x
			if poss and cv - v > obest:
				obest = cv - v
			if cv < 0:
				cv = 0
				poss = False
		else:
			cv = 0
print(obest)


import sys
from collections import defaultdict as dd
import heapq
import math
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
input = sys.stdin.readline
q = int(input())
w = list(map(int, input().split()))
ans = 0
for i in range(-30, 31):
	a = [-1000000000.0 if x > i else x for x in w]
	m = 0
	ma = 0
	for j in a:
		m += j
		if ma < m:
			ma = m
		elif m < 0:
			m = 0
	ans = max(ans, ma - i if i > 0 else ma)
print(ans)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline

	class Bit:

		def __init__(self, n):
			self.size = n
			self.tree = [0] * (n + 1)

		def sum(self, i):
			s = 0
			while i > 0:
				s += self.tree[i]
				i -= i & -i
			return s

		def add(self, i, x):
			while i <= self.size:
				self.tree[i] += x
				i += i & -i

		def lower_bound(self, w):
			if w <= 0:
				return 0
			x = 0
			k = 1 << self.size.bit_length() - 1
			while k:
				if x + k <= self.size and self.tree[x + k] < w:
					w -= self.tree[x + k]
					x += k
				k >>= 1
			return x + 1

	class SegmentTree:

		def __init__(self, A, initialize=True, segfunc=min, ident=2000000000):
			self.N = len(A)
			self.LV = (self.N - 1).bit_length()
			self.N0 = 1 << self.LV
			self.segfunc = segfunc
			self.ident = ident
			if initialize:
				self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
				for i in range(self.N0 - 1, 0, -1):
					self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
			else:
				self.data = [self.ident] * (self.N0 * 2)

		def update(self, i, x):
			i += self.N0 - 1
			self.data[i] = x
			for _ in range(self.LV):
				i >>= 1
				self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])

		def query(self, l, r):
			l += self.N0 - 1
			r += self.N0 - 1
			ret_l = self.ident
			ret_r = self.ident
			while l < r:
				if l & 1:
					ret_l = self.segfunc(ret_l, self.data[l])
					l += 1
				if r & 1:
					ret_r = self.segfunc(self.data[r - 1], ret_r)
					r -= 1
				l >>= 1
				r >>= 1
			return self.segfunc(ret_l, ret_r)
	N = int(input())
	A = list(map(int, input().split()))
	cs = [0] * (N + 1)
	B = []
	for (i, a) in enumerate(A):
		cs[i + 1] = cs[i] + A[i]
		B.append((a, i + 1))
	B.sort(key=lambda x: x[0], reverse=True)
	ma = SegmentTree(cs, segfunc=max, ident=-2000000000)
	mi = SegmentTree(cs)
	bit = Bit(N)
	ans = 0
	for (a, i) in B:
		if a <= 0:
			break
		bit.add(i, 1)
		k = bit.sum(i)
		r = bit.lower_bound(k + 1)
		l = bit.lower_bound(k - 1)
		ans = max(ans, ma.query(i + 1, r + 1) - mi.query(l + 1, i + 2) - a)
	print(ans)
main()


import sys
input = lambda : sys.stdin.readline().strip()
oo = 10 ** 9
n = int(input())
a = list(map(int, input().split()))
ans = 0
for mx in range(31):
	cur = 0
	prev = 0
	for i in range(n):
		val = -oo if a[i] > mx else a[i]
		cur += val
		prev = min(prev, cur)
		ans = max(ans, cur - prev - mx)
print(ans)


import sys, bisect, string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, groupby

def Golf():
	(n, *t) = map(int, open(0).read().split())

def I():
	return int(input())

def S_():
	return input()

def IS():
	return input().split()

def LS():
	return [i for i in input().split()]

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def StoLI():
	return [ord(i) - 97 for i in input()]

def ItoS(n):
	return chr(n + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def RA():
	return map(int, open(0).read().split())

def GI(V, E, ls=None, Directed=False, index=1):
	org_inp = []
	g = [[] for i in range(V)]
	FromStdin = True if ls == None else False
	for i in range(E):
		if FromStdin:
			inp = LI()
			org_inp.append(inp)
		else:
			inp = ls[i]
		if len(inp) == 2:
			(a, b) = inp
			c = 1
		else:
			(a, b, c) = inp
		if index == 1:
			a -= 1
			b -= 1
		aa = (a, c)
		bb = (b, c)
		g[a].append(bb)
		if not Directed:
			g[b].append(aa)
	return (g, org_inp)

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}, boundary=1):
	mp = [boundary] * (w + 2)
	found = {}
	for i in range(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [boundary] + [mp_def[j] for j in s] + [boundary]
	mp += [boundary] * (w + 2)
	return (h + 2, w + 2, mp, found)

def TI(n):
	return GI(n, n - 1)

def accum(ls):
	rt = [0]
	for i in ls:
		rt += [rt[-1] + i]
	return rt

def bit_combination(n, base=2):
	rt = []
	for tb in range(base ** n):
		s = [tb // base ** bt % base for bt in range(n)]
		rt += [s]
	return rt

def gcd(x, y):
	if y == 0:
		return x
	if x % y == 0:
		return y
	while x % y != 0:
		(x, y) = (y, x % y)
	return y

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = ['YES', 'NO']
Yn = ['Yes', 'No']
mo = 10 ** 9 + 7
inf = float('inf')
FourNb = [(-1, 0), (1, 0), (0, 1), (0, -1)]
EightNb = [(-1, 0), (1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
compas = dict(zip('WENS', FourNb))
cursol = dict(zip('LRUD', FourNb))
l_alp = string.ascii_lowercase
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()

class Tree:

	def __init__(self, inp_size=None, ls=None, init=True, index=0):
		self.LCA_init_stat = False
		self.ETtable = []
		if init:
			if ls == None:
				self.stdin(inp_size, index=index)
			else:
				self.size = len(ls) + 1
				(self.edges, _) = GI(self.size, self.size - 1, ls, index=index)
		return

	def stdin(self, inp_size=None, index=1):
		if inp_size == None:
			self.size = int(input())
		else:
			self.size = inp_size
		(self.edges, _) = GI(self.size, self.size - 1, index=index)
		return

	def listin(self, ls, index=0):
		self.size = len(ls) + 1
		(self.edges, _) = GI(self.size, self.size - 1, ls, index=index)
		return

	def __str__(self):
		return str(self.edges)

	def dfs(self, x, func=lambda prv, nx, dist: prv + dist, root_v=0):
		q = deque()
		q.append(x)
		v = [-1] * self.size
		v[x] = root_v
		while q:
			c = q.pop()
			for (nb, d) in self.edges[c]:
				if v[nb] == -1:
					q.append(nb)
					v[nb] = func(v[c], nb, d)
		return v

	def EulerTour(self, x):
		q = deque()
		q.append(x)
		self.depth = [None] * self.size
		self.depth[x] = 0
		self.ETtable = []
		self.ETdepth = []
		self.ETin = [-1] * self.size
		self.ETout = [-1] * self.size
		cnt = 0
		while q:
			c = q.pop()
			if c < 0:
				ce = ~c
			else:
				ce = c
				for (nb, d) in self.edges[ce]:
					if self.depth[nb] == None:
						q.append(~ce)
						q.append(nb)
						self.depth[nb] = self.depth[ce] + 1
			self.ETtable.append(ce)
			self.ETdepth.append(self.depth[ce])
			if self.ETin[ce] == -1:
				self.ETin[ce] = cnt
			else:
				self.ETout[ce] = cnt
			cnt += 1
		return

	def LCA_init(self, root):
		self.EulerTour(root)
		self.st = SparseTable(self.ETdepth, init_func=min, init_idl=inf)
		self.LCA_init_stat = True
		return

	def LCA(self, root, x, y):
		if self.LCA_init_stat == False:
			self.LCA_init(root)
		(xin, xout) = (self.ETin[x], self.ETout[x])
		(yin, yout) = (self.ETin[y], self.ETout[y])
		a = min(xin, yin)
		b = max(xout, yout, xin, yin)
		id_of_min_dep_in_et = self.st.query_id(a, b + 1)
		return self.ETtable[id_of_min_dep_in_et]

class SparseTable:

	def __init__(self, ls, init_func=min, init_idl=float('inf')):
		self.func = init_func
		self.idl = init_idl
		self.size = len(ls)
		self.N0 = self.size.bit_length()
		self.table = [ls[:]]
		self.index = [list(range(self.size))]
		self.lg = [0] * (self.size + 1)
		for i in range(2, self.size + 1):
			self.lg[i] = self.lg[i >> 1] + 1
		for i in range(self.N0):
			tmp = [self.func(self.table[i][j], self.table[i][min(j + (1 << i), self.size - 1)]) for j in range(self.size)]
			tmp_id = [self.index[i][j] if self.table[i][j] == self.func(self.table[i][j], self.table[i][min(j + (1 << i), self.size - 1)]) else self.index[i][min(j + (1 << i), self.size - 1)] for j in range(self.size)]
			self.table += [tmp]
			self.index += [tmp_id]

	def query(self, l, r):
		if r > self.size:
			r = self.size
		N = self.lg[r - l]
		return self.func(self.table[N][l], self.table[N][max(0, r - (1 << N))])

	def query_id(self, l, r):
		if r > self.size:
			r = self.size
		N = self.lg[r - l]
		(a, b) = (self.index[N][l], self.index[N][max(0, r - (1 << N))])
		if self.table[0][a] == self.func(self.table[N][l], self.table[N][max(0, r - (1 << N))]):
			b = a
		return b

	def right_bound(self, pos, x):
		k = (self.size - pos).bit_length()
		for j in range(k)[::-1]:
			nx = pos + (1 << j)
			if nx < n and self.query(pos, nx + 1) <= x:
				pos += 1 << j
		return pos

	def left_bound(self, pos, x):
		k = pos.bit_length()
		for j in range(k)[::-1]:
			nx = pos - (1 << j)
			if 0 <= nx and self.query(nx, pos + 1) <= x:
				pos -= 1 << j
		return pos

	def __str__(self):
		return str(self.table[0])

	def print(self):
		for i in self.table:
			print(*i)
show_flg = False
show_flg = True
ans = 0
n = I()
a = LI()
A = accum(a)
stmx = SparseTable(a, init_func=max, init_idl=float('inf'))
stmnA = SparseTable(A, init_func=min, init_idl=float('inf'))
stmxA = SparseTable(A, init_func=max, init_idl=float('inf'))
for i in range(n):
	r = stmx.right_bound(i, a[i])
	l = stmx.left_bound(i, a[i])
	M = stmxA.query(i + 1, r + 1 + 1)
	m = stmnA.query(l, i + 1)
	ans = max(M - m - a[i], ans)
print(ans)


from sys import stdin
input = stdin.buffer.readline
n = int(input())
(*a,) = map(int, input().split())
ans = 0
for x in range(0, 31):
	if not x in a:
		continue
	mx = a[0] if a[0] <= x else 0
	(sm, mn) = (0, 0)
	for i in range(n):
		if a[i] > x:
			continue
		sm += a[i]
		mx = max(mx, sm - mn)
		mn = min(mn, sm)
	ans = max(ans, mx - x)
print(ans)


from sys import stdin
input = stdin.buffer.readline
n = int(input())
aa = [int(i) for i in input().split()]
ans = -(10 ** 9 + 7)
for i in range(0, 31):
	msf = 0
	for j in range(0, n):
		if aa[j] <= i:
			msf += aa[j]
			msf = max(msf, 0)
			ans = max(ans, msf - i)
		else:
			msf = 0
print(ans)


from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

def solve():
	n = ri()
	A = rl()
	curr = {i: -10 ** 10 for i in range(-30, 31)}
	best = 0
	for a in A:
		nxt = dd(int)
		nxt[a] = max(a, curr[a] + a)
		for prev_max in range(-30, a):
			nxt[a] = max(nxt[a], curr[prev_max] + a)
			nxt[prev_max] = -10 ** 10
		best = max(best, nxt[a] - a)
		for prev_max in range(a + 1, 31):
			nxt[prev_max] = curr[prev_max] + a
			best = max(best, nxt[prev_max] - prev_max)
		curr = nxt
	print(best)
mode = 'S'
if mode == 'T':
	t = ri()
	for i in range(t):
		solve()
else:
	solve()


import copy
N = input()
N = int(N)
ints = input()
ints = [int(x) for x in ints.split(' ')]

def kadane(ints):
	cur_sum = 0
	best_sum = 0
	for x in ints:
		cur_sum = max(cur_sum + x, 0)
		best_sum = max(best_sum, cur_sum)
	return best_sum

def replace(ints, k):
	copy_ints = copy.copy(ints)
	for i in range(len(ints)):
		if copy_ints[i] > k:
			copy_ints[i] = float('-inf')
	return copy_ints

def solution(N, ints):
	if N == 1:
		return 0
	best_score = 0
	for i in range(1, 31):
		replaced_ints = replace(ints, i)
		score = kadane(replaced_ints) - i
		best_score = max(best_score, score)
	return best_score
print(solution(N, ints))


from sys import stdin
inp = lambda : stdin.readline().strip()
n = int(inp())
a = [int(x) for x in inp().split()]
ans = 0
for maximum in range(31):
	curr = 0
	best = 0
	for i in range(n):
		if a[i] <= maximum:
			val = a[i]
		else:
			val = -100000000000
		curr += val
		best = min(best, curr)
		ans = max(ans, curr - best - maximum)
print(ans)


MAX_VAL = 61
n = int(input())
lst = list(map(int, input().split(' ')))
msum = [[-10000000 for i in range(MAX_VAL)] for i in range(n)]
ans = -10000000
for i in reversed(range(n)):
	for j in range(lst[i], 31):
		msum[i][j] = lst[i] if i == n - 1 else max(msum[i + 1][j] + lst[i], lst[i])
		ans = max(ans, msum[i][j] - j)
print(int(ans))


production = True
import sys, math, collections

def input(input_format=0, multi=0):
	if multi > 0:
		return [input(input_format) for i in range(multi)]
	else:
		next_line = sys.stdin.readline()[:-1]
		if input_format >= 10:
			use_list = False
			input_format = int(str(input_format)[-1])
		else:
			use_list = True
		if input_format == 0:
			formatted_input = [next_line]
		elif input_format == 1:
			formatted_input = list(map(int, next_line.split()))
		elif input_format == 2:
			formatted_input = list(map(float, next_line.split()))
		elif input_format == 3:
			formatted_input = list(next_line)
		elif input_format == 4:
			formatted_input = list(map(int, list(next_line)))
		elif input_format == 5:
			formatted_input = next_line.split()
		else:
			formatted_input = [next_line]
		return formatted_input if use_list else formatted_input[0]

def out(output_line, output_format=0, newline=True):
	formatted_output = ''
	if output_format == 0:
		formatted_output = str(output_line)
	elif output_format == 1:
		formatted_output = ' '.join(map(str, output_line))
	elif output_format == 2:
		formatted_output = '\n'.join(map(str, output_line))
	print(formatted_output, end='\n' if newline else '')

def log(*args):
	if not production:
		print('$$$', end='')
		print(*args)
enu = enumerate
ter = lambda a, b, c: b if a else c

def mapl(iterable, format=0):
	if format == 0:
		return list(map(int, iterable))
	elif format == 1:
		return list(map(str, iterable))
	elif format == 2:
		return list(map(list, iterable))

def solve():
	n = input(11)
	a = input(1)
	ans = 0
	for mx in range(0, 31):
		cur = best = 0
		for i in a:
			if i > mx:
				continue
			cur += i
			best = min(best, cur)
			ans = max(ans, cur - best - mx)
	out(ans)
	return
solve()


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = 0
for M in range(-30, 31):
	acc = 0
	min_acc = 0
	for ai in a:
		acc += ai if ai <= M else -10 ** 18
		ans = max(ans, acc - min_acc - M)
		min_acc = min(min_acc, acc)
print(ans)


import sys
import string
input = sys.stdin.readline
import math
t = int(input())
for i in range(1):
	m = list(map(int, input().split()))
	best = 0
	if max(m) < 0:
		best = 2 * max(m)
	for a in range(0, 31):
		l = list(m)
		for k in range(len(l)):
			if l[k] > a:
				l[k] = -999999999
		sub_best = 0
		all_best = 0
		for k in range(len(l)):
			sub_best = sub_best + l[k]
			if sub_best < 0:
				sub_best = 0
			all_best = max(all_best, sub_best)
		best = max(best, all_best - a)
	print(best)


import sys
input = sys.stdin.readline
from math import ceil, floor, factorial

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def nCr(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0):
	hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(10000000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def factoriazation(x):
	ret = {}
	while x != 1:
		ret[spf[x]] = ret.get(spf[x], 0) + 1
		x = x // spf[x]
	return ret

def int_array():
	return list(map(int, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
n = int(input())
a = int_array()
ans = 0
for i in range(1, 31):
	this = a.copy()
	for j in range(n):
		if this[j] > i:
			this[j] = NINF
	x = 0
	d = 0
	mx = 0
	for j in this:
		mx = max(mx, j)
		x += j
		if x < 0:
			x = 0
			mx = 0
		d = max(x - mx, d)
	ans = max(ans, d)
print(ans)


i_kart = int(input())
lista = [int(x) for x in input().split()]
wynik = 0
for i in range(31):
	if lista[0] > i:
		max_local = max_total = 0
	else:
		max_local = max_total = lista[0]
	for x in lista[1:]:
		if x > i:
			continue
		max_local = max(x, max_local + x)
		max_total = max(max_total, max_local)
	wynik = max(wynik, max_total - i)
print(wynik)


import sys
from math import sqrt, ceil, factorial, inf
from collections import defaultdict as dd, deque, Counter as C
from decimal import Decimal
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
n = int(data())
arr = l()
answer = 0
for i in range(1, 31):
	s = 0
	for j in range(n):
		if arr[j] > i:
			continue
		s += arr[j]
		s = max(s, 0)
		answer = max(answer, s - i)
out(answer)


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
INF = 10 ** 12
ans = -INF
dp = [-INF] * 62
for (i, a) in enumerate(A):
	ndp = [-INF] * 62
	ndp[a] = max(0, dp[a] + a)
	for k in range(-30, a):
		ndp[a] = max(ndp[a], dp[k] + k)
	for k in range(a + 1, 31):
		ndp[a] = max(ndp[a], dp[k] + a)
	ans = max(ans, ndp[a])
	for k in range(a + 1, 31):
		ndp[k] = dp[k] + a
		ans = max(ans, ndp[k])
	dp = ndp
print(ans)


from sys import stdin, stdout
n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
ma_x = 0
c = 0
for i in arr:
	if i > ma_x:
		ma_x = i
	if i > 0:
		c += 1
if c == 1:
	ma_x = 0
ans = 0
for i in range(1, ma_x + 1):
	s = 0
	end = 0
	while end < n:
		s += arr[end]
		if arr[end] > i or s <= 0:
			s = 0
			start = end + 1
		ans = max(ans, s - i)
		end += 1
stdout.write(str(ans) + '\n')


import sys
ninf = -100000000
[n] = [int(i) for i in sys.stdin.readline().split()]
cards = [int(i) for i in sys.stdin.readline().split()]
dp = [[0 for i in range(n)] for j in range(61)]
for i in range(61):
	if cards[0] <= i - 30:
		dp[i][0] = cards[0]
	else:
		dp[i][0] = ninf
for j in range(1, n):
	for i in range(61):
		if cards[j] <= i - 30:
			dp[i][j] = max(dp[i][j - 1] + cards[j], cards[j])
		else:
			dp[i][j] = ninf
ans = 0
for j in range(n):
	for i in range(61):
		ans = max(ans, dp[i][j] - (i - 30))
print(ans)


def algo(i, j, arr, y):
	ans = maxi = t = 0
	for x in range(i, j + 1):
		maxi += arr[x]
		if maxi < 0:
			t = x + 1
			maxi = 0
		else:
			ans = max(ans, maxi - y)
	return ans
n = int(input())
arr = list(map(int, input().split()))
d = [[] for _ in range(1, 31)]
for i in range(n):
	if arr[i] > 0:
		d[arr[i] - 1].append(i)
ans = 0
for t in range(1, 31):
	se = set()
	for rr in d[t - 1]:
		if rr not in se:
			se.add(rr)
			i = 0
			fl = 0
			for i in range(rr - 1, -1, -1):
				if arr[i] > t:
					fl = 1
					break
				se.add(i)
			i += fl
			j = n - 1
			fl = 0
			for j in range(rr + 1, n):
				if arr[j] > t:
					fl = 1
					break
				se.add(j)
			j -= fl
			ans = max(ans, algo(i, j, arr, t))
print(ans)


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	for i in l:
		if i > 0:
			count += 1
	if count <= 1:
		print(0)
		return
	arr = [0] * 31
	for i in range(30, 0, -1):
		a = 0
		b = 0
		sub = 0
		for y in l:
			if y > i:
				a = 0
				b = 0
				continue
			b += y
			if sub < b - a:
				sub = b - a
			if b < a:
				a = b
		arr[i] = sub
	print(max([arr[i] - i for i in range(31)]))
solve()


from itertools import groupby
n = int(input())
a = list(map(int, input().split()))
INF = 100000000000000
dp = [[-INF] * 61 for i in range(n)]
ans = -INF
for i in range(n):
	if i == 0:
		dp[i][a[i] + 30] = 0
		continue
	dp[i][a[i] + 30] = 0
	for j in range(61):
		if dp[i - 1][j] == -INF:
			continue
		if j <= a[i] + 30:
			dp[i][a[i] + 30] = max(dp[i][a[i] + 30], dp[i - 1][j] + a[i] - (a[i] + 30 - j))
		else:
			dp[i][j] = dp[i - 1][j] + a[i]
	ans = max(ans, max(dp[i]))
print(max(ans, 0))


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return flag

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None
t = 1
for i in range(t):
	n = N()
	a = RLL()
	dp = [[-inf] * 61 for i in range(n)]
	dp[0][a[0] + 30] = a[0]
	ans = 0
	for i in range(1, n):
		for j in range(a[i] + 30, 61):
			if j == a[i] + 30:
				dp[i][j] = a[i]
				for k in range(31, j + 1):
					dp[i][j] = max(dp[i][j], dp[i - 1][k] + a[i])
				ans = max(ans, dp[i][j] - j + 30)
			else:
				dp[i][j] = max(dp[i][j], dp[i - 1][j] + a[i])
				ans = max(ans, dp[i][j] - j + 30)
	print(ans)


n = int(input())
l = list(map(int, input().split()))
d = set(l)
ans = 0
tot = 0
for j in range(31):
	if j not in d:
		continue
	tot = -999999999999999999999
	cur = 0
	for i in range(n):
		if l[i] > j:
			cur = 0
			continue
		else:
			cur += l[i]
			if cur < 0:
				cur = 0
			tot = max(tot, cur)
	ans = max(tot - j, ans)
print(ans)


INF = int(1000000000.0)

def kadane(temp):
	(sm, t) = (-INF, -INF)
	for x in temp:
		t = max(x, x + t)
		sm = max(sm, t)
	return sm
n = int(input())
arr = [int(x) for x in input().split()]
ans = 0
maxes = set([x for x in arr if x > 0])
for mx in maxes:
	temp = []
	for (ind, val) in enumerate(arr):
		if val > mx:
			temp.append(-INF)
		else:
			temp.append(val)
	ans = max(ans, kadane(temp) - mx)
print(ans)


def calc(x, mx):
	if x > mx:
		return float('-inf')
	else:
		return x

def calcmax(arr):
	max_so_far = float('-inf')
	currmax = 0
	for i in arr:
		currmax += i
		if currmax > max_so_far:
			max_so_far = currmax
		if currmax < 0:
			currmax = 0
	return max_so_far
n = int(input())
arr = [int(c) for c in input().split()]
ans = float('-inf')
for i in range(-30, 31):
	a = [calc(x, i) for x in arr]
	ans = max(ans, calcmax(a) - i)
print(ans)


from fractions import Fraction
import sys
import bisect
import heapq
from math import *
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
mod = pow(10, 9) + 7

def inp():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def graph(vertex):
	return [[] for i in range(0, vertex + 1)]

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def lcm(a, b):
	return a * b // gcd(a, b)

def solve():
	n = int(inp())
	a = lis()
	ans = []
	m = 0
	for j in range(30, -1, -1):
		currmax = 0
		temp = []
		f = False
		for i in range(0, n):
			if a[i] > j:
				currmax = 0
			else:
				currmax = max(currmax + a[i], 0)
				ans.append(currmax - j)
			if i == n - 1:
				if len(ans) == 0:
					ans.append(0)
				m = max(m, max(ans))
				ans = []
	print(m)
testcase(1)


import sys
input = sys.stdin.readline
from itertools import accumulate
n = int(input())
a = [0] + list(map(int, input().split()))
acc = list(accumulate(a))
mxls = [0]
ans = 0
l = 0
acmn = 1000000000
acmnls = [acmn] * (n + 1)
for i in range(1, n + 1):
	if mxls[i - 1] < a[i]:
		t = i
		mxls.append(a[i])
		while t >= 2 and mxls[t - 1] < a[i]:
			mxls[t - 1] = a[i]
			t -= 1
		acmn = acmnls[t - 1]
		for j in range(t, i + 1):
			acmn = min(acmn, acc[j - 1] + mxls[j])
			acmnls[j] = acmn
	else:
		mxls.append(a[i])
		acmn = min(acmn, acc[i - 1] + mxls[i])
		acmnls[i] = acmn
	ans = max(ans, acc[i] - acmn)
print(ans)


import sys
input = sys.stdin.readline
from itertools import accumulate
n = int(input())
A = list(map(int, input().split()))
S = [0] + list(accumulate(A))
import heapq
XMIN = [[] for i in range(61)]
XMAX = [[] for i in range(61)]
for i in range(n):
	XMIN[A[i] + 30].append(i)
	XMAX[A[i] + 30].append(-i)
for i in range(61):
	heapq.heapify(XMIN[i])
	heapq.heapify(XMAX[i])
seg_el = 1 << (n + 2).bit_length()
SEGMIN = [1 << 30] * (2 * seg_el)
SEGMAX = [-1 << 30] * (2 * seg_el)
for i in range(n + 1):
	SEGMIN[i + seg_el] = S[i]
	SEGMAX[i + seg_el] = S[i]
for i in range(seg_el - 1, 0, -1):
	SEGMIN[i] = min(SEGMIN[i * 2], SEGMIN[i * 2 + 1])
	SEGMAX[i] = max(SEGMAX[i * 2], SEGMAX[i * 2 + 1])

def update(n):
	i = n + seg_el
	SEGMIN[i] = 1 << 30
	SEGMAX[i] = -1 << 30
	i >>= 1
	while i != 0:
		SEGMIN[i] = min(SEGMIN[i * 2], SEGMIN[i * 2 + 1])
		SEGMAX[i] = max(SEGMAX[i * 2], SEGMAX[i * 2 + 1])
		i >>= 1

def getvalues_min(l, r):
	L = l + seg_el
	R = r + seg_el
	ANS = 1 << 30
	while L < R:
		if L & 1:
			ANS = min(ANS, SEGMIN[L])
			L += 1
		if R & 1:
			R -= 1
			ANS = min(ANS, SEGMIN[R])
		L >>= 1
		R >>= 1
	return ANS

def getvalues_max(l, r):
	L = l + seg_el
	R = r + seg_el
	ANS = -1 << 30
	while L < R:
		if L & 1:
			ANS = max(ANS, SEGMAX[L])
			L += 1
		if R & 1:
			R -= 1
			ANS = max(ANS, SEGMAX[R])
		L >>= 1
		R >>= 1
	return ANS
A1 = [0] * n
A2 = [0] * n
for i in range(n):
	v = A[i] + 30
	MIN = n + 1
	for j in range(v + 1, 61):
		while XMIN[j] and XMIN[j][0] < i:
			heapq.heappop(XMIN[j])
		if XMIN[j]:
			MIN = min(MIN, XMIN[j][0])
	A1[i] = max(0, getvalues_max(i + 2, MIN + 1) - S[i + 1])
for i in range(n - 1, -1, -1):
	v = A[i] + 30
	MAX = -1
	for j in range(v + 1, 61):
		while XMAX[j] and -XMAX[j][0] > i:
			heapq.heappop(XMAX[j])
		if XMAX[j]:
			MAX = max(MAX, -XMAX[j][0])
	A2[i] = max(0, S[i] - getvalues_min(MAX + 1, i + 1))
ANS = 0
for i in range(n):
	ANS = max(ANS, A1[i] + A2[i])
print(ANS)


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
PI = 3.141592653589793
INF = float('inf')
MOD = 1000000007

def bin32(num):
	return '{0:032b}'.format(num)

def add(x, y):
	return (x + y) % MOD

def sub(x, y):
	return (x - y + MOD) % MOD

def mul(x, y):
	return x * y % MOD

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def lcm(x, y):
	return x * y // gcd(x, y)

def power(x, y):
	res = 1
	x %= MOD
	while y != 0:
		if y & 1:
			res = mul(res, x)
		y >>= 1
		x = mul(x, x)
	return res

def mod_inv(n):
	return power(n, MOD - 2)

def prob(p, q):
	return mul(p, power(q, MOD - 2))

def ii():
	return int(input())

def li():
	return [int(i) for i in input().split()]

def ls():
	return [i for i in input().split()]
n = ii()
a = li()
dp = [[-INF for i in range(62)] for j in range(n)]
dp[0][a[0] + 30] = 0
ans = 0
for i in range(1, n):
	x = a[i] + 30
	for j in range(x + 1):
		dp[i][x] = max(dp[i][x], dp[i - 1][j] + j - 30, 0)
		ans = max(ans, dp[i][j])
	for j in range(x + 1, 62):
		dp[i][j] = max(dp[i][j], dp[i - 1][j] + a[i])
		ans = max(ans, dp[i][j])
print(ans)


def solution(a):
	ans = 0
	for mx in range(31):
		cum_sum = 0
		cum_sum_min = 0
		for val in a:
			cum_sum += -10000000.0 if val > mx else val
			cum_sum_min = min(cum_sum_min, cum_sum)
			ans = max(ans, cum_sum - cum_sum_min - mx)
	return ans
n = int(input())
a = list(map(int, input().split()))
print(int(solution(a)))


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import sys

def main():
	n = int(input())
	A = tuple(map(int, input().split()))
	DP = [[-float('inf')] * 61 for _ in range(n + 1)]
	DP[0][30] = 0
	for (i, a) in enumerate(A):
		DP[i + 1][a + 30] = 0
		for j in range(61):
			c = j - 30
			if a >= c:
				DP[i + 1][a + 30] = max(DP[i + 1][a + 30], DP[i][j] + c)
			else:
				DP[i + 1][j] = DP[i][j] + a
	ans = 0
	for dp in DP:
		ans = max(ans, max(dp))
	sys.stdout.write(str(ans) + '\n')
main()


from collections import defaultdict
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange

def print_case_iterable(case_num, iterable):
	print('Case #{}: {}'.format(case_num, ' '.join(map(str, iterable))))

def print_case_number(case_num, iterable):
	print('Case #{}: {}'.format(case_num, iterable))

def print_iterable(A):
	print(' '.join(A))

def read_int():
	return int(f.readline().strip())

def read_int_array():
	return [int(x) for x in f.readline().strip().split(' ')]

def rns():
	a = [x for x in f.readline().split(' ')]
	return (int(a[0]), a[1].strip())

def read_string():
	return list(f.readline().strip())

def bi(x):
	return bin(x)[2:]
from collections import deque
import math

def regular_bs(L, x, l=None, r=None):
	l = 0 if l == None else l
	r = len(L) if r == None else r
	while r - l > 1:
		m = (r + l) // 2
		l = m if L[m] <= x else l
		r = m if L[m] > x else r
	cnt = 0
	return l

def solution(A, n):
	total_max = 0
	d = defaultdict(list)
	elems = set(A)
	for x in elems:
		if x > 0:
			d[x].append(-1)
	for i in range(n):
		if A[i] <= 0:
			continue
		for x in range(1, A[i]):
			if x in elems:
				d[x].append(i)
	for x in elems:
		if x > 0:
			d[x].append(n)
	for m in elems:
		for j in range(1, len(d[m])):
			start = d[m][j - 1] + 1
			end = d[m][j]
			max_so_far = 0
			max_end_here = 0
			saw_max = False
			for i in range(start, end):
				x = A[i]
				if x == m and (not saw_max):
					saw_max = True
					max_so_far = max(max_so_far, max_end_here)
					continue
				max_end_here = max_end_here + x
				if saw_max:
					max_so_far = max(max_so_far, max_end_here)
				if saw_max and max_end_here <= -m or (not saw_max and max_end_here <= 0):
					saw_max = False
					max_end_here = 0
			total_max = max(total_max, max_so_far)
	return total_max

def main():
	T = 1
	for i in range(T):
		n = read_int()
		A = read_int_array()
		x = solution(A, n)
		if 'xrange' not in dir(__builtins__):
			print(x)
		else:
			(print >> output, str(x))
	if 'xrange' in dir(__builtins__):
		print(output.getvalue())
		output.close()
if 'xrange' in dir(__builtins__):
	import cStringIO
	output = cStringIO.StringIO()
main()


from itertools import accumulate
import sys
input = sys.stdin.readline

class SegTree:

	def __init__(self, init_val, n, ide_ele, seg_func):
		self.segfunc = seg_func
		self.num = 2 ** (n - 1).bit_length()
		self.ide_ele = ide_ele
		self.seg = [self.ide_ele] * 2 * self.num
		for i in range(n):
			self.seg[i + self.num - 1] = init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, k, x):
		k += self.num - 1
		self.seg[k] = x
		while k + 1:
			k = (k - 1) // 2
			self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

	def query(self, p, q):
		if q <= p:
			return self.ide_ele
		p += self.num - 1
		q += self.num - 2
		res = self.ide_ele
		while q - p > 1:
			if p & 1 == 0:
				res = self.segfunc(res, self.seg[p])
			if q & 1 == 1:
				res = self.segfunc(res, self.seg[q])
				q -= 1
			p = p // 2
			q = (q - 1) // 2
		if p == q:
			res = self.segfunc(res, self.seg[p])
		else:
			res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
		return res
n = int(input())
xs = [0] + list(map(int, input().split()))
X = list(accumulate(xs))
xis = [(i, x) for (i, x) in enumerate(xs)]
xis = sorted(xis, key=lambda x: x[1])[::-1]
bx = None
tmp = []
F = [(0, n + 1)] * (n + 1)
sti1 = SegTree([0] * (n + 1), n + 1, -1, max)
sti2 = SegTree([n + 1] * (n + 1), n + 1, 10 ** 18, min)
for (i, x) in xis:
	if bx == x:
		pass
	else:
		for j in tmp:
			sti1.update(j, j)
			sti2.update(j, j)
		tmp = []
	F[i] = (sti1.query(0, i), sti2.query(i, n + 1))
	tmp.append(i)
	bx = x
st1 = SegTree(X, n + 1, -10 ** 18, max)
st2 = SegTree(X, n + 1, 10 ** 18, min)
R = 0
for i in range(1, n + 1):
	(k, l) = F[i]
	R = max(R, st1.query(i, l) - st2.query(k, i) - xs[i])
print(R)


a = int(input())
z = list(map(int, input().split()))
res = 0
ans = 0
for i in range(1, 31):
	res = 0
	for j in range(len(z)):
		res += z[j]
		if z[j] > i:
			res = 0
		res = max(res, 0)
		ans = max(ans, res - i)
print(ans)


n = int(input())
a = list(map(int, input().split()))
max_sum = 0
for j in range(1, 31):
	if j not in a:
		continue
	dp = [0 for i in range(n)]
	dp[0] = a[0]
	valid_sums = []
	prev = False
	for i in range(n):
		if a[i] <= j:
			if prev:
				dp[i] = max(0, a[i], a[i] + dp[i - 1])
				if a[i] == j:
					valid = True
					valid_sums.append(dp[i])
				elif valid:
					valid_sums.append(a[i] + dp[i - 1])
			else:
				dp[i] = a[i]
				prev = True
				if a[i] == j:
					valid = True
					valid_sums.append(dp[i])
				else:
					valid = False
		else:
			prev = False
			valid = False
	max_sum = max(max_sum, max(valid_sums) - j)
print(max_sum)


def mcss(l, r):
	if l > r:
		return 0
	s = 0
	ret = 0
	for i in range(l, r + 1):
		s += aa[i]
		ret = max(ret, s)
		s = max(s, 0)
	return ret
n = int(input())
aa = list(map(int, input().split()))
ans = 0
for maxa in range(1, 31):
	l = 0
	for (r, a) in enumerate(aa):
		if a > maxa:
			ans = max(ans, mcss(l, r - 1) - maxa)
			l = r + 1
	ans = max(ans, mcss(l, n - 1) - maxa)
print(ans)


import sys

def I():
	return sys.stdin.readline().rstrip()

def f(l):
	m = max(l)
	if m <= 0:
		return 0
	s = 0
	ms = 0
	for x in l:
		s += x
		ms = max(ms, s)
		s = max(s, 0)
	ans = max(ms - m, 0)
	le = 0
	ri = -1
	while le < len(l):
		le = ri + 1
		ri = le
		while ri < len(l) and l[ri] < m:
			ri += 1
		if le < ri - 1:
			ans = max(ans, f(l[le:ri]))
	return ans
I()
print(f(list(map(int, I().split()))))


N = int(input())
As = list(map(int, input().split()))
dp = [-100] * 70
dp[0] = 0
ans = 0
for (i, A) in enumerate(As):
	new_dp = [-100] * 70
	new_dp[A] = A
	for ma in range(-30, A + 1):
		new_dp[A] = max(new_dp[A], dp[ma] + A)
	for ma in range(A + 1, 31):
		new_dp[ma] = dp[ma] + A
	dp = new_dp
	ans = max(ans, max((dp[i] - i for i in range(-30, 31))))
print(ans)


def rs():
	return input().strip()

def ri():
	return int(input())

def ria():
	return list(map(int, input().split()))

def ia_to_s(a):
	return ' '.join([str(s) for s in a])

def solve(n, a):
	ans = 0
	for i in range(31):
		s = 0
		for j in a:
			if j <= i:
				s = max(0, s + j)
			else:
				s = 0
			ans = max(ans, s - i)
	return ans

def main():
	n = ri()
	a = ria()
	print(solve(n, a))
main()


def do(arr):
	res = 0
	for i in range(30, -31, -1):
		temp = 0
		for x in arr:
			if x > i:
				temp = 0
			else:
				res = max(res, temp + x - i)
				temp = max(0, temp + x)
	return res
input()
lst = list(map(int, input().split()))
print(do(lst))


def run(arr):
	ans = 0
	inf = 10 ** 9
	for mx in range(0, 31):
		cur = 0
		best = 0
		for x in arr:
			cur += -inf if x > mx else x
			best = min(cur, best)
			ans = max(ans, cur - best - mx)
	return ans

def main():
	from sys import stdin
	import os
	if os.path.exists('tmp.in'):
		stdin = open('tmp.in')
	n = int(stdin.readline())
	arr = [int(x) for x in stdin.readline().split()]
	ans = run(arr)
	print(ans)
main()


import sys
n = int(input())
a = [int(x) for x in input().split()]
ans = 0
for mx in range(-30, 31):
	cur = 0
	for i in range(n):
		v = 1
		if a[i] > mx:
			cur = 0
			v = 0
		else:
			cur += a[i]
		if cur < 0:
			v = 0
			cur = 0
		if v:
			ans = max(ans, cur - mx)
print(ans)


inf = int(1000000.0)
n = int(input())
lis = list(map(int, input().split()))
final = 0
for i in range(30, 0, -1):
	s = 0
	ans = 0
	for j in range(n):
		a = lis[j]
		if lis[j] > i:
			a = -inf
		s += a
		s = max(0, s)
		ans = max(ans, s)
	final = max(ans - i, final)
print(final)


n = int(input())
a = list(map(int, input().split())) + [100]
ans = 0
for i in range(-30, 31):
	b = []
	for x in a:
		if x <= i:
			b.append(x)
		elif b:
			m = 0
			t = 0
			for y in b:
				t += y
				ans = max(ans, t - m - i)
				m = min(m, t)
			b = []
print(ans)


import sys
input = sys.stdin.readline
flush = sys.stdout.flush

def buildM():
	for i in reversed(range(1, n)):
		segM[i] = max(segM[2 * i], segM[2 * i + 1])
	return

def buildS():
	for i in reversed(range(1, n + 1)):
		segSM[i] = max(segSM[2 * i], segSM[2 * i + 1])
		segSm[i] = min(segSm[2 * i], segSm[2 * i + 1])
	return

def queryM(l, r):
	res = -31
	l += n
	r += n
	while l < r:
		if l & 1:
			res = max(res, segM[l])
			l += 1
		if r & 1:
			r -= 1
			res = max(res, segM[r])
		l >>= 1
		r >>= 1
	return res

def querySM(l, r):
	res = -30 * 10 ** 5 - 1
	l += n + 1
	r += n + 1
	while l < r:
		if l & 1:
			res = max(res, segSM[l])
			l += 1
		if r & 1:
			r -= 1
			res = max(res, segSM[r])
		l >>= 1
		r >>= 1
	return res

def querySm(l, r):
	res = 30 * 10 ** 5 + 1
	l += n + 1
	r += n + 1
	while l < r:
		if l & 1:
			res = min(res, segSm[l])
			l += 1
		if r & 1:
			r -= 1
			res = min(res, segSm[r])
		l >>= 1
		r >>= 1
	return res
n = int(input())
a = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
	S[i + 1] = S[i] + a[i]
segM = [0] * n + a
segSM = [0] * (n + 1) + S
segSm = [0] * (n + 1) + S
buildM()
buildS()
ans = -10 ** 9
for (i, x) in enumerate(a):
	score = 0
	l = 0
	r = i
	while l < r:
		m = l + r >> 1
		if queryM(m, i + 1) == x:
			r = m
		else:
			l = m + 1
	ll = l
	l = i
	r = n - 1
	while l < r:
		m = (l + r >> 1) + 1
		if queryM(i, m + 1) == x:
			l = m
		else:
			r = m - 1
	rr = r
	score += S[i] - querySm(ll, i + 1)
	score += querySM(i + 1, rr + 2) - S[i + 1]
	if score > ans:
		ans = score
print(ans)


INF = -1000000000
n = int(input())
a = list(map(int, input().split()))
ans = 0
for mx in range(31):
	cur = 0
	best = 0
	for i in range(n):
		if a[i] > mx:
			val = INF
		else:
			val = a[i]
		cur += val
		best = min(best, cur)
		ans = max(ans, cur - best - mx)
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
mx = 1
ans = 0
while mx <= 30:
	loc = 0
	for x in a:
		if x > mx:
			loc = 0
			continue
		loc += x
		if loc < 0:
			loc = 0
		ans = max(ans, loc - mx)
	mx += 1
print(ans)


from sys import stdin
input = stdin.readline

def main():
	test = 1
	for _ in range(test):
		n = int(input())
		ara = [int(x) for x in input().split()]
		ans = 0
		for mx in range(min(ara), max(ara) + 1):
			sum = 0
			for x in ara:
				sum += x
				if x > mx or sum < 0:
					sum = 0
					continue
				ans = max(ans, sum - mx)
		print(ans)
main()


N = int(input())
A = [int(_) for _ in input().split()]
dp = [[0] * 63 for _ in range(N + 1)]
dp[0][A[0] + 30] = A[0]
answer = 0
for i in range(1, N):
	el = A[i]
	iel = el + 30
	dp[i][iel] = max(dp[i][iel], el)
	answer = max(answer, dp[i][iel] - max(el, 0))
	for m in range(-30, 31):
		im = m + 30
		if el > m:
			dp[i][iel] = max(dp[i][iel], dp[i - 1][im] + el)
			answer = max(answer, dp[i][iel] - max(el, 0))
		elif dp[i - 1][im] > 0:
			dp[i][im] = max(dp[i][im], dp[i - 1][im] + el)
			answer = max(answer, dp[i][im] - max(m, 0))
print(answer)


a = []
n = 0

def tryit(mx):
	gs = 0
	cs = 0
	cmx = -float('inf')
	for i in a:
		if i > mx:
			cs = 0
			cmx = -float('inf')
			continue
		cs = max(i, cs + i)
		if cs == i:
			cmx = i
		cmx = max(cmx, i)
		gs = max(gs, cs - cmx)
	return gs
n = int(input())
a = list(map(int, input().split()))
cs = 0
gs = 0
mx = -float('inf')
ans = 0
for i in range(-30, 31):
	ans = max(ans, tryit(i))
print(ans)


n = int(input())
l = list(map(int, input().split()))
ans = 0
s = set()
for i in l:
	if i > 0:
		s.add(i)
for i in s:
	now = 0
	for j in l:
		if j > i:
			now -= float('INF')
		else:
			now += j
		if now <= 0:
			now = 0
		else:
			ans = max(ans, now - i)
print(ans)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def YES():
	print('YES')

def NO():
	print('NO')

def Yes():
	print('Yes')

def No():
	print('No')
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		self.num_sets -= 1
		self.parent[a] = b
		self.size[b] += self.size[a]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def lcm(a, b):
	return abs(a // gcd(a, b) * b)

def solve():
	n = N()
	ar = lis()
	inf = float('inf')

	def find(ar, n):
		dp = [ar[0]]
		for i in range(1, n):
			dp.append(max(dp[-1] + ar[i], ar[i]))
		return max(dp)
	m = -inf
	for i in range(-30, 31):
		new = []
		for j in range(n):
			if ar[j] > i:
				new.append(-inf)
			else:
				new.append(ar[j])
		v = find(new, n)
		m = max(v - i, m)
	print(m)
solve()


import sys

def I():
	return sys.stdin.readline().rstrip()

def f(l, st, en):
	m = -1
	for i in range(st, en):
		m = max(m, l[i])
	if m <= 0:
		return 0
	s = 0
	ms = 0
	for i in range(st, en):
		x = l[i]
		s += x
		ms = max(ms, s)
		s = max(s, 0)
	ans = max(ms - m, 0)
	le = st
	ri = st - 1
	while le < en:
		le = ri + 1
		ri = le
		while ri < en and l[ri] < m:
			ri += 1
		if le < ri - 1:
			ans = max(ans, f(l, le, ri))
	return ans
n = int(I())
print(f(list(map(int, I().split())), 0, n))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
import bisect
from collections import Counter
import bisect

def maxSubArraySum(a, size):
	ls = a.copy()
	if ls[0] > j:
		ls[0] = -10 ** 20
		max_so_far = 0
		curr_max = 0
	else:
		max_so_far = ls[0]
		curr_max = ls[0]
	for i in range(1, size):
		if ls[i] > j:
			ls[i] = -10 ** 20
		curr_max = max(ls[i], curr_max + ls[i])
		max_so_far = max(max_so_far, curr_max)
	return max_so_far
n = int(input())
arr = list(map(int, input().split()))
ans = 0
for j in range(1, 31):
	if j not in arr:
		continue
	ans = max(ans, maxSubArraySum(arr, n) - j)
print(ans)


n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(-30, 31):
	b = [int(-1000000000.0) if x > i else x for x in a]
	dp = b.copy()
	for j in range(1, n):
		dp[j] = max(dp[j - 1] + b[j], b[j])
	ans = max(ans, max(dp) - i)
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 9
ans = -INF
for mx in range(31):
	b = [0] * n
	for i in range(n):
		if a[i] > mx:
			b[i] = -INF
		else:
			b[i] = a[i]
	dp = [0] * n
	dp[0] = max(b[0], 0)
	for i in range(1, n):
		dp[i] = max(0, dp[i - 1] + b[i], b[i])
	res = max(dp) - mx
	ans = max(ans, res)
print(ans)


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop
import math
from collections import *
from functools import reduce, cmp_to_key, lru_cache
from itertools import accumulate
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = mod = 10 ** 9 + 7

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip().split()]

def st():
	return str(input().rstrip())[2:-1]

def val():
	return int(input().rstrip())

def li2():
	return [str(i)[2:-1] for i in input().rstrip().split()]

def li3():
	return [int(i) for i in st()]

class Node:

	def __init__(self, s, e):
		self.start = s
		self.end = e
		self.val = 0
		self.left = None
		self.right = None

def build(nums, l, r):
	if l == r:
		temp = Node(l, l)
		temp.val = nums[l]
	else:
		mid = l + r >> 1
		temp = Node(l, r)
		temp.left = build(nums, l, mid)
		temp.right = build(nums, mid + 1, r)
		temp.val = max(temp.left.val, temp.right.val)
	return temp

def query(root, start, end):
	if root.start >= start and root.end <= end:
		return root.val
	elif root.start > end or root.end < start:
		return -float('inf')
	else:
		temp1 = query(root.left, start, end)
		temp2 = query(root.right, start, end)
		return max(temp1, temp2)
n = val()
l = li()
d = defaultdict(list)
for i in range(n):
	d[l[i]].append(i)
pref1 = [0]
for i in l:
	pref1.append(i + pref1[-1])
pref1 = pref1[1:]
pref2 = [0]
for i in l[::-1]:
	pref2.append(pref2[-1] + i)
pref2 = pref2[1:][::-1]
root1 = build(pref1, 0, n - 1)
root2 = build(pref2, 0, n - 1)
ans = 0
lows = [0]
q = deque()
q.append(0)
for i in range(1, n):
	while q and l[q[-1]] <= l[i]:
		q.pop()
	lows.append(q[-1] + 1 if q else 0)
	q.append(i)
high = [n - 1]
q = deque()
q.append(n - 1)
for i in range(n - 2, -1, -1):
	while q and l[q[-1]] <= l[i]:
		q.pop()
	high.append(q[-1] - 1 if q else n - 1)
	q.append(i)
high = high[::-1]
for i in range(n):
	a1 = query(root2, lows[i], i)
	a2 = query(root1, i, high[i])
	ans = max(ans, a1 + a2 - pref1[i] - pref2[i])
print(ans)


def solve(n, ar):
	ans = 0
	for i in range(1, 31):
		sum = 0
		for j in range(n):
			if sum < 0:
				sum = 0
			sum += ar[j]
			if ar[j] > i:
				sum = 0
			if sum - i > ans:
				ans = sum - i
	print(ans)
n = int(input())
ar = list(map(int, input().split()))
solve(n, ar)


from collections import deque
from sys import stdin
input = stdin.readline
INF = 10 ** 9 + 7
MAX = 10 ** 7 + 7
MOD = 10 ** 9 + 7
n = int(input().strip())
a = [int(x) for x in input().strip().split()]
ans = 0
for mxi in range(31):
	(cs, s) = (float('-inf'), float('-inf'))
	for i in range(n):
		c = a[i] if a[i] <= mxi else float('-inf')
		cs = max(cs + c, c)
		s = max(s, cs)
	ans = max(ans, s - mxi)
print(ans)


def max_subarray(li, x):
	if len(li) == 0:
		return 0
	li = [0] + li
	min_so_far = [0]
	index = -1
	ans = 0
	for p in range(1, len(li)):
		if li[p] == x:
			index = p
		li[p] += li[p - 1]
		if index != -1:
			ans = max(ans, li[p] - min_so_far[index - 1])
		min_so_far.append(min(min_so_far[p - 1], li[p]))
	return max(0, ans - x)
t = 1
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	l = []
	for i in range(31):
		l.append([-1])
	for i in range(n):
		for j in range(1, s[i]):
			l[j].append(i)
	for j in range(1, 31):
		l[j].append(n)
	ans = 0
	for i in range(30, 0, -1):
		for j in range(1, len(l[i])):
			p = max_subarray(s[l[i][j - 1] + 1:l[i][j]], i)
			ans = max(ans, p)
	print(ans)


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	c = dict(Counter(l))
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieveForSmallestPrimeFactor():
	MAXN = 100001
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf

def getPrimeFactorizationLOGN(x):
	spf = sieveForSmallestPrimeFactor()
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def si():
	return input()

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def kandane(l, n):
	mx_so_far = 0
	mx_cur = 0
	for i in range(n):
		mx_cur += l[i]
		mx_cur = max(mx_cur, 0)
		mx_so_far = max(mx_cur, mx_so_far)
	return mx_so_far

def solve():
	n = ii()
	l = li()
	ans = 0
	l1 = list(set(l[:]))
	l1.sort(reverse=True)
	for i in l1:
		if i < 0:
			break
		a = l[:]
		for j in range(n):
			if a[j] > i:
				a[j] = -float('inf')
		ans = max(ans, kandane(a, n) - i)
	print(ans)
t = 1
for _ in range(t):
	solve()


from copy import deepcopy

def max_sub(L: list) -> int:
	j = -1
	cur = 0
	max_sum = 0
	while len(L) != (j := (j + 1)):
		cur += L[j]
		if cur < 0:
			cur = 0
			continue
		if cur > max_sum:
			max_sum = cur
	return max_sum

def compute(L: list) -> int:
	L_dup = deepcopy(L)
	cur = 0
	for i in range(30, 0, -1):
		L_dup = [-30 * 10000000.0 if x > i else x for x in L_dup]
		max_sum = max_sub(L_dup)
		if cur < max_sum - i:
			cur = max_sum - i
	return cur
n = int(input())
L = [int(x) for x in input().split()]
print(compute(L))


inf = 10 ** 9
n = int(input())
l = list(map(int, input().split()))
ans = 0
for i in range(31):
	cur = 0
	best = 0
	for j in range(n):
		cval = -inf
		if l[j] <= i:
			cval = l[j]
		cur += cval
		best = min(best, cur)
		ans = max(ans, cur - best - i)
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
a = [0] + a
f = [None for i in range(n + 1)]
g = [0 for i in range(n + 1)]
ans = 0
for m in range(-30, 31):
	for i in range(1, n + 1):
		g[i] = 0 if a[i] > m else max(0, g[i - 1] + a[i])
		if f[i - 1] is None:
			f[i] = None if a[i] != m else m + g[i - 1]
		elif a[i] == m:
			f[i] = g[i - 1] + m
		elif a[i] < m:
			f[i] = f[i - 1] + a[i]
		else:
			f[i] = None
	for i in range(1, n + 1):
		if f[i] is not None:
			ans = max(ans, f[i] - m)
print(ans)


n = int(input())
l = list(map(int, input().split()))
m = 0
for x in range(1, 31):
	s = 0
	for i in range(n):
		if l[i] > x:
			s = 0
		else:
			s += l[i]
			m = max(m, s - x)
			if s < 0:
				s = 0
print(m)


n = int(input())
a = list(map(int, input().split()))
s = 0
ss = [0] * 31
ss_ind = [0] * 31
met = [False] * 31
sums = [a[0]]
for i in range(1, n):
	sums.append(sums[-1] + a[i])
ans = 0
for i in range(n):
	if a[i] >= 0:
		met[a[i]] = True
	for j in range(31):
		if a[i] > j:
			ss[j] = 0
			met[j] = False
		elif ss[j] + a[i] < 0:
			ss[j] = 0
			met[j] = False
		else:
			ss[j] += a[i]
			if met[j]:
				ans = max(ans, ss[j] - j)
print(ans)


import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f

def eprint(*args):
	print(*args, file=sys.stderr)
zz = 1
from math import *
import copy
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')

def li():
	return [int(x) for x in input().split()]

def fi():
	return int(input())

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def bo(i):
	return ord(i) - ord('a')
tt = 1

def subs(a, p, d):
	c = 0
	for i in range(n):
		if a[i] > p:
			c = 0
			d[i] = 0
			continue
		elif c + a[i] > a[i]:
			c += a[i]
			if c < 0:
				c = 0
			d[i] = c
		else:
			c = a[i]
			if c < 0:
				c = 0
			d[i] = c
while tt > 0:
	tt -= 1
	n = fi()
	d = [0 for i in range(65)]
	a = li()
	pre = [[0 for i in range(n + 1)] for j in range(62)]
	suf = [[0 for i in range(n + 1)] for j in range(62)]
	maxi = 0
	for i in range(-30, 31):
		subs(a, i, pre[i + 30])
		subs(a[::-1], i, suf[i + 30])
	for i in range(n):
		if i == 0:
			maxi = max(maxi, suf[a[i] + 30][n - i - 2])
		elif i == n - 1:
			maxi = max(maxi, pre[a[i] + 30][i - 1])
		else:
			maxi = max(maxi, pre[a[i] + 30][i - 1] + suf[a[i] + 30][n - i - 2])
	print(maxi)


from sys import stdin, gettrace
if not gettrace():

	def input():
		return next(stdin)[:-1]

def main():
	n = int(input())
	aa = [int(a) for a in input().split()]
	mlss = [0] * n
	dp = [[0] * 31]
	for a in aa[:-1]:
		dp.append([0] * 31)
		for i in range(max(0, a), 31):
			dp[-1][i] = max(0, dp[-2][i] + a)
	for i in range(1, n):
		mlss[i] = dp[i][max(aa[i], 0)]
	mrss = [0] * n
	dp = [[0] * 31]
	for a in aa[-1:0:-1]:
		dp.append([0] * 31)
		for i in range(max(0, a), 31):
			dp[-1][i] = max(0, dp[-2][i] + a)
	dp.reverse()
	for i in range(n - 2, -1, -1):
		mrss[i] = dp[i][max(aa[i], 0)]
	best = 0
	for (a, mls, mrs) in zip(aa, mlss, mrss):
		best = max(best, mls + mrs)
	print(best)
main()


from math import ceil
n = int(input())
arr = [int(x) for x in input().split()]
ans = 0
for i in range(1, 31):
	res = 0
	for each in arr:
		res += each
		if each > i:
			res = 0
		res = max(res, 0)
		ans = max(res - i, 0, ans)
print(ans)


import sys
n = int(input())
arr = list(map(int, input().split()))
ans = 0
for i in range(30, 0, -1):
	maxsum = 0
	for j in range(n):
		if arr[j] > i:
			maxsum = 0
			continue
		maxsum += arr[j]
		maxsum = max(maxsum, 0)
		ans = max(ans, maxsum - i)
print(ans)


import io
import os
from collections import Counter, defaultdict, deque

class RangeQuery:

	def __init__(self, data, func=min):
		self.func = func
		self._data = _data = [list(data)]
		(i, n) = (1, len(_data[0]))
		while 2 * i <= n:
			prev = _data[-1]
			_data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
			i <<= 1

	def query(self, start, stop):
		assert start < stop
		depth = (stop - start).bit_length() - 1
		return self.func(self._data[depth][start], self._data[depth][stop - (1 << depth)])

def buildFirstBigger(arr):
	ret = [None] * len(arr)
	window = []
	for (i, x) in enumerate(arr):
		while window and window[-1][1] <= x:
			window.pop()
		if window:
			assert window[-1][1] > x
			ret[i] = window[-1][0]
		window.append((i, x))
	return ret
DEBUG = False

def solve(N, A):
	pref = [0]
	for x in A:
		pref.append(pref[-1] + x)
	rangeMin = RangeQuery(pref, min)
	rangeMax = RangeQuery(pref, max)
	firstBiggerLeft = buildFirstBigger(A)
	firstBiggerRight = [N - 1 - i if i is not None else None for i in buildFirstBigger(A[::-1])[::-1]]
	if DEBUG:
		for i in range(N):
			leftIndex = firstBiggerLeft[i]
			if leftIndex is not None:
				assert A[leftIndex] > A[i]
				assert max(A[leftIndex + 1:i], default=float('-inf')) <= A[i]
			rightIndex = firstBiggerRight[i]
			if rightIndex is not None:
				assert A[rightIndex] > A[i]
				assert max(A[i + 1:rightIndex], default=float('-inf')) <= A[i]
	best = 0
	for i in range(N):
		leftIndex = firstBiggerLeft[i]
		if leftIndex is None:
			leftIndex = 0
		else:
			leftIndex += 1
		leftSum = 0
		if leftIndex < i:
			leftSum = max(0, pref[i] - rangeMin.query(leftIndex, i))
		rightIndex = firstBiggerRight[i]
		if rightIndex is None:
			rightIndex = N + 1
		rightSum = 0
		if i + 1 < rightIndex:
			rightSum = max(0, rangeMax.query(i + 1, rightIndex) - pref[i + 1])
		best = max(best, leftSum + rightSum)
	return best
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = solve(N, A)
print(ans)


n = int(input())
a = list(map(int, input().split()))
ans = 0
for m in range(1, 31):
	now = 0
	for v in a:
		if v > m:
			now = 0
			continue
		now = max(now + v, 0)
		ans = max(ans, now - m)
print(ans)


from sys import stdin
input = stdin.readline
from collections import deque
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
n = I()
a = list(R())
ans = 0
for mx in range(31):
	best = cur = 0
	for i in a:
		v = -1 if i > mx else i
		cur += v
		best = min(best, cur)
		ans = max(ans, cur - best - mx)
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = 0
for M in range(-30, 31):
	b = a[:]
	for i in range(n):
		if b[i] > M:
			b[i] = -10 ** 18
	acc = 0
	min_acc = 0
	for bi in b:
		acc += bi
		ans = max(ans, acc - min_acc - M)
		min_acc = min(min_acc, acc)
print(ans)


def findMax(a, cand, prefix):
	heap = []
	minPrefix = 0
	result = float('-inf')
	maxSeen = float('-inf')
	for i in range(1, len(prefix)):
		maxSeen = max(maxSeen, a[i - 1])
		if maxSeen > cand:
			maxSeen = float('-inf')
			minPrefix = i
		else:
			if maxSeen == cand:
				result = max(result, prefix[i] - prefix[minPrefix] - maxSeen)
			if prefix[i] < prefix[minPrefix]:
				minPrefix = i
	return result
n = int(input())
a = [int(x) for x in input().split()]
prefix = [0]
for val in a:
	prefix.append(prefix[-1] + val)
result = 0
for cand in range(-30, 31):
	result = max(result, findMax(a, cand, prefix))
print(result)


import sys
input = sys.stdin.readline

def build(a, index, beg, end, tree):
	if beg == end:
		tree[index][0] = a[beg]
		tree[index][1] = a[beg]
	else:
		mid = (beg + end) // 2
		build(a, 2 * index + 1, beg, mid, tree)
		build(a, 2 * index + 2, mid + 1, end, tree)
		tree[index][0] = tree[2 * index + 1][0] + tree[2 * index + 2][0]
		tree[index][1] = max(tree[2 * index + 1][1], tree[2 * index + 1][0] + tree[2 * index + 2][1])

def query(index, beg, end, l, r):
	result = [-1, -1]
	if beg > r or end < l:
		return result
	if beg >= l and end <= r:
		return tree[index]
	mid = (beg + end) // 2
	if l > mid:
		return query(2 * index + 2, mid + 1, end, l, r)
	if r <= mid:
		return query(2 * index + 1, beg, mid, l, r)
	left = query(2 * index + 1, beg, mid, l, r)
	right = query(2 * index + 2, mid + 1, end, l, r)
	result[0] = left[0] + right[0]
	result[1] = max(left[1], left[0] + right[1])
	return result
n = int(input())
arr = list(map(int, input().split()))
tree = [[0, 0] for j in range(3 * n)]
build(arr, 0, 0, n - 1, tree)
fw = [0 for k in range(n)]
bw = [0 for k in range(n)]
cur_max = bw[n - 1] = arr[n - 1]
i = n - 2
p = [n - 1]
bw[n - 1] = 0
d = dict()
q = 0
d[arr[n - 1]] = n - 1
while i >= 0:
	if arr[i] > 0:
		r = 1000000
		for j in range(arr[i] + 1, 31):
			if j in d.keys():
				r = min(r, d[j])
		if r > p[0]:
			bw[i] = max(0, cur_max)
		else:
			bw[i] = max(0, query(0, 0, n - 1, i + 1, r - 1)[1])
	cur_max = max(arr[i], cur_max + arr[i])
	if arr[i] == cur_max:
		p = [i]
		q = 1
	else:
		p.append(i)
		q += 1
	d[arr[i]] = i
	i += -1
tree = [[0, 0] for j in range(3 * n)]
build(arr[::-1], 0, 0, n - 1, tree)
(cur_max, max_so_far) = (arr[0], arr[0])
p = [0]
q = 0
d = dict()
d[arr[0]] = 0
for i in range(1, n):
	if arr[i] > 0:
		r = -1
		for j in range(arr[i] + 1, 31):
			if j in d.keys():
				r = max(r, d[j])
		if r < p[0]:
			fw[i] = max(0, cur_max)
		else:
			fw[i] = max(0, query(0, 0, n - 1, n - 1 - i + 1, n - 1 - r - 1)[1])
	cur_max = max(arr[i], cur_max + arr[i])
	if arr[i] == cur_max:
		p = [i]
		q = 1
	else:
		p.append(i)
		q += 1
	d[arr[i]] = i
f = 0
f = max(f, fw[n - 1], bw[0])
j = 1
while j < n - 1:
	f = max(f, fw[j] + bw[j])
	j += 1
print(f)


import sys
input = sys.stdin.readline

def prog():
	n = int(input())
	cards = list(map(int, input().split()))
	maxes = [0]
	for m in range(1, 31):
		ans = 0
		value = 0
		for card in cards:
			if card <= m:
				value = max(card, value + card)
			else:
				value = 0
			ans = max(value, ans)
		maxes.append(ans - m)
	print(max(maxes))
prog()


from sys import stdin, stdout

def yet_another_yet_another_task(a):
	n = len(a)
	preSum = [0 for i in range(n)]
	postSum = [0 for i in range(n)]
	preSum[0] = a[0]
	postSum[n - 1] = a[n - 1]
	for i in range(1, n):
		preSum[i] = preSum[i - 1] + a[i]
	for i in range(n - 2, -1, -1):
		postSum[i] = postSum[i + 1] + a[i]
	preSumSegmentTree = SegmentTree(0, n - 1, preSum)
	postSumSegmentTree = SegmentTree(0, n - 1, postSum)
	st = []
	leftSum = [0 for i in range(n)]
	for i in range(n):
		j = i
		while len(st) > 0 and st[-1][0] <= a[i]:
			j = st.pop()[1]
		st.append([a[i], j])
		leftSum[i] = postSumSegmentTree.query(j, i) - postSum[i]
	st = []
	rightSum = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		j = i
		while len(st) > 0 and st[-1][0] <= a[i]:
			j = st.pop()[1]
		st.append([a[i], j])
		rightSum[i] = preSumSegmentTree.query(i, j) - preSum[i]
	res = 0
	for i in range(n):
		res = max(res, leftSum[i] + rightSum[i])
	return res

class SegmentTree:

	def __init__(self, i, j, sum):
		self.l = i
		self.r = j
		m = (i + j) // 2
		if i == j:
			self.maxVal = sum[i]
			return
		if i > j:
			return -1000000000
		self.lst = SegmentTree(i, m, sum)
		self.rst = SegmentTree(m + 1, j, sum)
		if self.lst is not None and self.rst is not None:
			self.maxVal = max(self.lst.maxVal, self.rst.maxVal)
		elif self.lst is None:
			self.maxVal = self.rst.maxVal
		elif self.rst is None:
			self.maxVal = self.lst.maxVal

	def query(self, i, j):
		if j < self.l or self.r < i:
			return -1000000000
		if i <= self.l and self.r <= j:
			return self.maxVal
		ql = -1000000000
		qr = -1000000000
		if self.lst is not None:
			ql = self.lst.query(i, j)
		if self.rst is not None:
			qr = self.rst.query(i, j)
		return max(ql, qr)

def yet_another_yet_another_task2(a):
	res = 0
	for i in range(1, 31):
		mxr = 0
		mnr = 0
		for j in a:
			if j > i:
				mxr = 0
				mnr = 0
			else:
				mxr += j
				mnr = min(mxr, mnr)
				res = max(res, mxr - mnr - i)
	return res
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
stdout.write(str(yet_another_yet_another_task(a)) + '\n')


n = int(input())
A = list(map(int, input().split()))
s = max(A)
ans = 0
for val in range(s, 0, -1):
	(mv, cv) = (0, 0)
	for i in range(n):
		if A[i] <= val:
			cv = cv + A[i]
			mv = max(mv, cv)
			if cv < 0:
				cv = 0
		else:
			cv = 0
		ans = max(mv - val, ans)
print(ans)


q = int(input())
w = list(map(int, input().split()))
ans = 0
for i in range(-30, 31):
	a = [-1000000000.0 if x > i else x for x in w]
	m = 0
	ma = 0
	for j in a:
		m += j
		if ma < m:
			ma = m
		elif m < 0:
			m = 0
	ans = max(ans, ma - i if i > 0 else ma)
print(ans)


import sys
input = sys.stdin.readline
import heapq
import copy
import math
import decimal
from decimal import *

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

class Node:

	def _init_(self, val):
		self.data = val
		self.left = None
		self.right = None

class fen_tree:

	def __init__(self, list):
		self.array = [0] + list
		for idx in range(1, len(self.array)):
			idx2 = idx + (idx & -idx)
			if idx2 < len(self.array):
				self.array[idx2] += self.array[idx]

	def prefix_query(self, idx):
		result = 0
		while idx:
			result += self.array[idx]
			idx -= idx & -idx
		return result

	def prints(self):
		print(self.array)
		return

	def range_query(self, from_idx, to_idx):
		return self.prefix_query(to_idx) - self.prefix_query(from_idx - 1)

	def update(self, idx, add):
		while idx < len(self.array):
			self.array[idx] += add
			idx += idx & -idx

def pre_sum(arr):
	p = [0]
	for i in arr:
		p.append(p[-1] + i)
	p.pop(0)
	return p

def pre_back(arr):
	p = [0]
	for i in arr:
		p.append(p[-1] + i)
	p.pop(0)
	return p

def bin_search(arr, l, r, val):
	if arr[r] <= val:
		return r + 1
	if r - l < 2:
		if arr[l] > val:
			return l
		else:
			return r
	mid = int((l + r) / 2)
	if arr[mid] <= val:
		return bin_search(arr, mid, r, val)
	else:
		return bin_search(arr, l, mid, val)

def search_leftmost(arr, val):

	def helper(arr, l, r, val):
		print(l, r)
		if arr[l] == val:
			return l
		if r - l <= 1:
			if arr[r] == val:
				return r
			else:
				print('not found')
				return
		mid = int((r + l) / 2)
		if arr[mid] >= val:
			return helper(arr, l, mid, val)
		else:
			return helper(arr, mid, r, val)
	return helper(arr, 0, len(arr) - 1, val)

def search_rightmost(arr, val):

	def helper(arr, l, r, val):
		print(l, r)
		if arr[r] == val:
			return r
		if r - l <= 1:
			if arr[l] == val:
				return r
			else:
				print('not found')
				return
		mid = int((r + l) / 2)
		if arr[mid] > val:
			return helper(arr, l, mid, val)
		else:
			return helper(arr, mid, r, val)
	return helper(arr, 0, len(arr) - 1, val)

def preorder_postorder(root, paths, parent, left, level):
	l = 0
	queue = [root]
	while queue != []:
		node = queue[-1]
		flag = 0
		for i in paths[node]:
			if i != parent[node] and level[i] == sys.maxsize:
				parent[i] = node
				level[i] = level[node] + 1
				flag = 1
				queue.append(i)
		if flag == 0:
			left[parent[node]] += 1 + left[node]
			queue.pop()
	return [parent, left, level]

def pr_list(a):
	print(*a, sep=' ')

def main():
	tests = 1
	mod = 1000000007
	limit = 10 ** 18
	for test in range(tests):
		n = inp()
		a = inlt()
		dp = [[-100 for i in range(61)] for j in range(n)]
		dp[0][a[0] + 30] = 0
		ans = 0
		for i in range(1, n):
			curr = 0
			for j in range(0, a[i] + 1 + 30):
				if dp[i - 1][j] > -100:
					curr = max(curr, dp[i - 1][j] + (j - 30))
			dp[i][a[i] + 30] = max(curr, 0)
			ans = max(ans, dp[i][a[i] + 30])
			for j in range(a[i] + 1 + 30, 61):
				if dp[i - 1][j] != -100:
					dp[i][j] = dp[i - 1][j] + a[i]
					ans = max(ans, dp[i][j])
		print(ans)
main()


n = int(input())
arr = list(map(int, input().split()))
ans = 0
for i in range(1, 31):
	mu_now = 0
	fin = 0
	for j in range(n):
		if arr[j] > i:
			fin = 0
			mu_now = 0
			continue
		mu_now += arr[j]
		if arr[j] == i:
			fin = 1
		mu_now = max(mu_now, 0)
		if fin:
			ans = max(ans, mu_now - i)
print(ans)


import sys
input = sys.stdin.readline

def main():
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for m in range(31):
		v = 0
		for x in a:
			if x > m:
				v = 0
			else:
				v = max(v, 0) + x
				ans = max(ans, v - m)
	print(ans)
main()


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from bisect import *
import sys

def main():
	n = int(input())
	a = list(map(int, input().split()))
	b = max(a)
	ma = 0
	mi = -10000000
	for i in range(b, 0, -1):
		max_value = 0
		max_so_far = 0
		f = 0
		for j in range(n):
			max_so_far += a[j]
			if a[j] > i:
				max_so_far -= a[j]
				max_so_far += mi
			if max_so_far < 0:
				max_so_far = 0
			if max_value < max_so_far:
				max_value = max_so_far
		ma = max(ma, max_value - i)
	print(ma)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
mx = 0
cur = [0] * 30
for i in range(30):
	cur[i] = [0, 0]
for i in a:
	for j in range(30):
		if i == j + 1 and cur[j][1] == 0:
			cur[j][1] = i
			cur[j][0] -= i
		cur[j][0] += i
		if i > j + 1:
			cur[j][0] = 0
			cur[j][1] = 0
		if cur[j][0] < 0:
			if cur[j][1] == 0:
				cur[j][0] = 0
			elif cur[j][0] < -j:
				cur[j][0] = 0
				cur[j][1] = 0
		if cur[j][0] > mx and cur[j][1] > 0:
			mx = cur[j][0]
print(mx)


from sys import stdin
inp = lambda : stdin.readline().strip()
n = int(inp())
a = [int(x) for x in inp().split()]
ans = 0
for maximum in range(max(a) + 1):
	subArray = 0
	for i in range(n):
		val = a[i] if a[i] <= maximum else -100000000000
		subArray = max(subArray + val, val)
		ans = max(ans, subArray - maximum)
print(ans)


import sys
buff_readline = sys.stdin.readline
readline = sys.stdin.readline
INF = 2 ** 62 - 1

def read_int():
	return int(buff_readline())

def read_int_n():
	return list(map(int, buff_readline().split()))

def read_float():
	return float(buff_readline())

def read_float_n():
	return list(map(float, buff_readline().split()))

def read_str():
	return readline().strip()

def read_str_n():
	return readline().strip().split()

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

def slv(N, A):
	from collections import Counter
	memo = {}
	memo[0] = 0
	ans = 0
	for a in A:
		nm = Counter()
		for (k, v) in memo.items():
			m = max(k, a)
			nm[m] = max(nm[m], v + a)
			ans = max(ans, nm[m] - m)
		nm[0] = 0
		memo = nm
	return ans

def main():
	N = read_int()
	A = read_int_n()
	print(slv(N, A))
main()


import sys
import heapq

def main():
	n = int(input())
	nums = list(map(int, sys.stdin.readline().split()))
	ans = 0
	for i in range(-30, 31):
		tempAns = 0
		for j in range(n):
			tempAns += nums[j]
			if nums[j] > i:
				tempAns = -31 * n
			ans = max(ans, tempAns - i)
			if tempAns < 0:
				tempAns = 0
	print(ans)
	return
main()


import sys
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def read():
	tc = 0
	if tc:
		input = sys.stdin.readline
	else:
		sys.stdin = open('input1.txt', 'r')
		sys.stdout = open('output1.txt', 'w')

def solve():
	n = ii()
	a = li()

	def get(x):
		ans = -1000000000.0
		i = 0
		while i < n:
			if a[i] > x:
				i += 1
				continue
			j = i
			cur = 0
			while j < n:
				if a[j] > x:
					break
				else:
					cur += a[j]
				ans = max(ans, cur)
				if cur < 0:
					cur = 0
				j += 1
			i = j
		return ans - x
	ans = 0
	for i in range(-30, 31):
		ans = max(ans, get(i))
	print(ans)
solve()


INF = 100000000000000000000000000000000000000000000000000
(n, a, resp) = (int(input()), list(map(int, input().split())), 0)
for ale in range(31):
	(corrente, melhor) = (0, 0)
	for i in range(n):
		val = -INF if a[i] > ale else a[i]
		corrente += val
		melhor = min(melhor, corrente)
		resp = max(resp, corrente - melhor - ale)
print(resp)


def solve(n, d):
	maxScore = 0
	maxer = float('-inf')
	res = 0
	for i in range(31):
		sub = float('-inf')
		curr = float('-inf')
		for j in range(len(d)):
			now = d[j]
			if d[j] > i:
				now = float('-inf')
			sub = max(sub + now, now)
			curr = max(curr, sub)
			res = max(curr - i, res)
	return res

def main():
	n = int(input())
	d = input()
	d = [int(i) for i in d.split()]
	ans = solve(n, d)
	print(ans)
main()


n = int(input())
arr = list(map(int, input().rstrip().split()))
ans = 0
for maxNum in range(30, 0, -1):
	maxSum = 0
	for pos in range(len(arr)):
		if arr[pos] > maxNum:
			maxSum = 0
			continue
		maxSum += arr[pos]
		maxSum = max(maxSum, 0)
		ans = max(ans, maxSum - maxNum)
print(ans)