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.
import io
import os

from collections import Counter, defaultdict, deque

# From: https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/RangeQuery.py
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):
        """func of data[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):
    # Returns an array with index of first element bigger to the left
    ret = [None] * len(arr)
    window = []  # Window of (index, value), value strictly decreasing
    for i, x in enumerate(arr):
        # Pop anything not strictly greater than x
        while window and window[-1][1] <= x:
            window.pop()
        if window:
            # Last element of window is first element on the left that is bigger than x
            assert window[-1][1] > x
            ret[i] = window[-1][0]
        # Insert x, maintaining the strictly decreasing subsequence invariant.
        window.append((i, x))
    return ret


DEBUG = False


def solve(N, A):
    # Precompute the min and max cumulative sum in any range
    pref = [0]
    for x in A:
        pref.append(pref[-1] + x)
    rangeMin = RangeQuery(pref, min)
    rangeMax = RangeQuery(pref, max)

    # Precompute the first element greater to the left of A[i]
    firstBiggerLeft = buildFirstBigger(A)
    # Precompute the first element greater to the right of A[i]
    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):
        # Get longest range to left and right that are less than or equal to A[i]
        # Get min and max cumulative sum in those ranges
        # Use them to get best range sum by taking the delta with current sum

        # Maximize pref[i] - pref[j]
        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))

        # Maximize pref[j] - pref[i + 1]
        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


if __name__ == "__main__":
    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)
