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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.stream.IntStream;

public class d {
    public static void main(String[] args) {
        FS in = new FS(System.in);
        PrintWriter out = new PrintWriter(System.out);
        
//        int t = in.nextInt(); while(t-->0)
        new d().solve(in, out);
        
        out.close();
    }
    
    void solve(FS in, PrintWriter out) {
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = in.nextInt();
        int[] pref = new int[n+1];
        for(int i = 0; i < n; i++) pref[i+1] = pref[i]+arr[i];
        Node tree = new Node(0, n+1, pref);
        
       int[] left = new int[n];
       ArrayDeque<Integer> q = new ArrayDeque<>();
       for(int i = 0; i < n; i++) {
           int prev = -1;
           while(!q.isEmpty() && arr[q.peekLast()] <= arr[i]) {
               q.pollLast();
           }
           if(!q.isEmpty()) prev = q.peekLast();
           left[i] = pref[i]-tree.min(prev+1, i+1);
           q.addLast(i);
       }
       q.clear();
       int[] right = new int[n];
       q.clear();
       for(int i = n-1; i >= 0; i--) {
           int prev = n;
           while(!q.isEmpty() && arr[q.peekLast()] <= arr[i]) {
               q.pollLast();
           }
           if(!q.isEmpty()) prev = q.peekLast();
           right[i] = tree.max(i+1, prev+1)-pref[i+1];
           q.addLast(i);
       }
       int max = Integer.MIN_VALUE;
       for(int i = 0; i < n; i++) max = Math.max(max, left[i]+right[i]);
       out.println(max);
    }
    
    static class Node {
        int l, r, max, min;
        Node left, right;
        
        public Node(int le, int ri, int[] arr) {
            l = le;
            r = ri;
            if(l == r-1) {
                max = min = arr[l];
                return;
            }
            
            int mid = (l+r)/2;
            left = new Node(l, mid, arr);
            right = new Node(mid, r, arr);
            max = Math.max(left.max, right.max);
            min = Math.min(left.min, right.min);
        }
        
        int max(int le, int ri) {
            if(le <= l && ri >= r) return max;
            if(le >= r || ri <= l) return Integer.MIN_VALUE/2;
            return Math.max(left.max(le, ri), right.max(le, ri));
        }
        int min(int le, int ri) {
            if(le <= l && ri >= r) return min;
            if(le >= r || ri <= l) return Integer.MAX_VALUE/2;
            return Math.min(left.min(le, ri), right.min(le, ri));
        }
    }
    
    static class FS {

        BufferedReader in;
        StringTokenizer token;
        
        public FS(InputStream str) {
            in = new BufferedReader(new InputStreamReader(str));
        }
        
        public String next() {
            if (token == null || !token.hasMoreElements()) {
                try {
                    token = new StringTokenizer(in.readLine());
                } catch (IOException ex) {
                }
                return next();
            }
            return token.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(next());
        }
    }
}