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.
// Spaghetti code
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    static int mod=(int)(1e9+7);
    static int mod2=998244353;
    static PrintWriter pw;
    static class FastReader
    {
        private InputStream mIs;private byte[] buf = new byte[1024];private int curChar,numChars;public FastReader() { this(System.in); }public FastReader(InputStream is) { mIs = is;}
        public int read() {if (numChars == -1) throw new InputMismatchException();if (curChar >= numChars) {curChar = 0;try { numChars = mIs.read(buf);} catch (IOException e) { throw new InputMismatchException();}if (numChars <= 0) return -1; }return buf[curChar++];}
        public String nextLine(){int c = read();while (isSpaceChar(c)) c = read();StringBuilder res = new StringBuilder();do {res.appendCodePoint(c);c = read();}while (!isEndOfLine(c));return res.toString() ;}
        public String next(){int c = read();while (isSpaceChar(c)) c = read();StringBuilder res = new StringBuilder();do {res.appendCodePoint(c);c = read();}while (!isSpaceChar(c));return res.toString();}
        public long l(){int c = read();while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }long res = 0; do{ if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read();}while(!isSpaceChar(c));return res * sgn;}
        public int i(){int c = read() ;while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }int res = 0;do{if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read() ;}while(!isSpaceChar(c));return res * sgn;}
        public double d() throws IOException {return Double.parseDouble(next()) ;}
        public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; }
        public boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; }
        public void scanIntArr(int [] arr){ for(int li=0;li<arr.length;++li)arr[li]=i();}
        public void scanIntIndexArr(int [] arr){ for(int li=0;li<arr.length;++li){ arr[li]=i()-1;}}
        public void printIntArr(int [] arr){ for(int li=0;li<arr.length;++li)pw.print(arr[li]+" ");pw.println();}
        public void printLongArr(long [] arr){ for(int li=0;li<arr.length;++li)pw.print(arr[li]+" ");pw.println();}
        public void scanLongArr(long [] arr){for (int i=0;i<arr.length;++i){arr[i]=l();}}
        public void shuffle(int [] arr){ for(int i=arr.length;i>0;--i) { int r=(int)(Math.random()*i); int temp=arr[i-1]; arr[i-1]=arr[r]; arr[r]=temp; }}
        public int swapIntegers(int a,int b){return a;} //Call it like this: a=swapIntegers(b,b=a)
        public int findMax(int [] arr){int res=Integer.MIN_VALUE;for(int num:arr)res=Math.max(res,num);return res;}

    }

    public static void main(String[] args) throws IOException {

        FastReader fr = new FastReader();
        pw = new PrintWriter(System.out);

     /*
inputCopy
5
5 -2 10 -1 4
outputCopy
6
inputCopy
8
5 2 5 3 -30 -30 6 9
outputCopy
10
inputCopy
3
-10 6 -15
outputCopy
0
    */
        //Press Ctrl+Win+Alt+L for reformatting indentation

        int t = 1;

        for (int ti = 0; ti < t; ++ti) {
            int n = fr.i();
            int[] arr = new int[n];
            fr.scanIntArr(arr);

            int ans = 0, curSum = 0, maxSum = 0;
            for (int curMax = 1; curMax <= 30; ++curMax) {
                for (int ni = 0; ni < n; ++ni) {
                    curSum += arr[ni] > curMax ? Integer.MIN_VALUE : arr[ni];
                    if (curSum < 0) curSum = 0;
                    else if (curSum > maxSum)
                        maxSum = curSum;
                }
                ans = Math.max(ans, maxSum - curMax);
                curSum = 0;
                maxSum = 0;
            }
            pw.println(ans);
        }
        pw.flush();
        pw.close();
    }
}