Alice and Bob are playing yet another card game. This time the rules are the following. There are n cards lying in a row in front of them. The i-th card has value a_i. 

First, Alice chooses a non-empty consecutive segment of cards [l; r] (l ≤ r). After that Bob removes a single card j from that segment (l ≤ j ≤ r). The score of the game is the total value of the remaining cards on the segment (a_l + a_{l + 1} + ... + a_{j - 1} + a_{j + 1} + ... + a_{r - 1} + a_r). In particular, if Alice chooses a segment with just one element, then the score after Bob removes the only card is 0.

Alice wants to make the score as big as possible. Bob takes such a card that the score is as small as possible.

What segment should Alice choose so that the score is maximum possible? Output the maximum score.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of cards.

The second line contains n integers a_1, a_2, ..., a_n (-30 ≤ a_i ≤ 30) — the values on the cards.

Output

Print a single integer — the final score of the game.

Examples

Input


5
5 -2 10 -1 4


Output


6


Input


8
5 2 5 3 -30 -30 6 9


Output


10


Input


3
-10 6 -15


Output


0

Note

In the first example Alice chooses a segment [1;5] — the entire row of cards. Bob removes card 3 with the value 10 from the segment. Thus, the final score is 5 + (-2) + (-1) + 4 = 6.

In the second example Alice chooses a segment [1;4], so that Bob removes either card 1 or 3 with the value 5, making the answer 5 + 2 + 3 = 10.

In the third example Alice can choose any of the segments of length 1: [1;1], [2;2] or [3;3]. Bob removes the only card, so the score is 0. If Alice chooses some other segment then the answer will be less than 0.
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
# import sys
# input = sys.stdin.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)
