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 java.io.*;
import java.util.*;

public class r88p4{

    private static InputReader sc;
    private static PrintWriter pw;

    static class InputReader {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

        InputReader(InputStream stream) {
            this.stream = stream;
        }

        int snext() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        int nextInt() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        long nextLong() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        String readString() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        String nextLine() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = snext();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        public interface SpaceCharFilter {
            boolean isSpaceChar(int ch);
        }
    }

    public static void main(String args[]) {
        sc = new InputReader(System.in);
        pw = new PrintWriter(System.out);

        int t = 1;
        while(t-->0)
            solve();

        pw.flush();
        pw.close();
    }

    private static int[] get_arr(int arr[], int begin, int end){
        if(end - begin + 1 < 1)
            return new int[0];

        int res[] = new int[end - begin + 1];

        for(int i=begin; i<=end; i++)
            res[i-begin] = arr[i];

        return res;
    }

    private static long get_max(int arr[]){
        int n = arr.length;

        if(n <= 1)  return 0;

        int max = Integer.MIN_VALUE;
        long ans = 0;

        for(int i=0; i<n; i++)
            max = Math.max(max, arr[i]);

        ArrayList<Integer> pos = new ArrayList<>();

        for(int i=0; i<n; i++){
            if(arr[i] == max)
                pos.add(i);
        }

        int temp[] = get_arr(arr, 0, pos.get(0)-1);
        ans = get_max(temp);

        for(int i=0; i<pos.size()-1; i++){
            temp = get_arr(arr, pos.get(i)+1, pos.get(i+1)-1);
            ans = Math.max(ans, get_max(temp));
        }

        temp = get_arr(arr, pos.get(pos.size()-1)+1, n-1);
        ans = Math.max(ans, get_max(temp));

        long pre[] = new long[pos.size()], post[] = new long[pos.size()], sum[] = new long[pos.size()];

        for(int i=0; i<pos.size(); i++)
        {
            long pre_temp = 0, post_temp = 0;
            int curr_pos = pos.get(i), prev_pos, next_pos;

            prev_pos = (i == 0)? -1 : pos.get(i-1);
            next_pos = (i == pos.size()-1)? n : pos.get(i+1);

            for(int j=curr_pos-1; j>prev_pos; j--){
                pre_temp += arr[j];
                pre[i] = Math.max(pre_temp, pre[i]);
            }

            for(int j=curr_pos+1; j<next_pos; j++){
                post_temp += arr[j];
                post[i] = Math.max(post[i], post_temp);
            }

            sum[i] = post_temp;
        }

        long max_pre = pre[0];

        for(int i=0; i<pos.size(); i++){
            max_pre = Math.max(max_pre, pre[i]);

            ans = Math.max(ans, max_pre + post[i]);

            max_pre += sum[i] + max;
        }

        return ans;
    }

    private static void solve(){
        int n = sc.nextInt(), arr[] = new int[n];

        for(int i=0; i<n; i++)
            arr[i] = sc.nextInt();

        pw.println(get_max(arr));
    }
}