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 Main{
    static int minArr[][];
    static int maxArr[][];
    public static void main(String args[])
    {
        FastReader input=new FastReader();
        PrintWriter out=new PrintWriter(System.out);
        int T=1;
        while(T-->0)
        {
            int n=input.nextInt();
            minArr=new int[n+1][30];
            maxArr=new int[n+1][30];
            int a[]=new int[n+1];
            ArrayList<Integer> arr[]=new ArrayList[61];
            ArrayList<Integer> arr1[]=new ArrayList[61];
            for(int i=0;i<=60;i++)
            {
                arr[i]=new ArrayList<>();
                arr1[i]=new ArrayList<>();
            }
            int preArr[]=new int[n+1];
            for(int i=1;i<=n;i++)
            {
                a[i]=input.nextInt();
                preArr[i]=a[i]+preArr[i-1];
                int v=a[i]+30;
                arr[v].add(i);
                arr1[v].add(i);
            }
            for(int i=1;i<=60;i++)
            {
                Collections.sort(arr[i],Collections.reverseOrder());
                Collections.sort(arr1[i]);
            }
            int range[][]=new int[n+1][2];
            for(int i=1;i<=n;i++)
            {
                int v=a[i]+30;
                arr[v].remove(arr[v].size()-1);
                int minInd=n+1;
                for(int j=v+1;j<=60;j++)
                {
                    if(arr[j].size()>0)
                    {
                        int ind=arr[j].get(arr[j].size()-1);
                        minInd=Math.min(minInd,ind);
                    }
                }
                range[i][1]=minInd-1;
            }
            for(int i=n;i>=1;i--)
            {
                int v=a[i]+30;
                arr1[v].remove(arr1[v].size()-1);
                int maxInd=0;
                for(int j=v+1;j<=60;j++)
                {
                    if(arr1[j].size()>0)
                    {
                        int ind=arr1[j].get(arr1[j].size()-1);
                        maxInd=Math.max(maxInd,ind);
                    }
                }
                range[i][0]=maxInd+1;
            }
            createArrayMax(preArr,n);
            createArrayMin(preArr,n);
            int maxDiff=0;
            for(int i=1;i<=n;i++)
            {
                int l=range[i][0];
                int r=range[i][1];
                int min=getMin(l-1,i-1);
                int max=getMax(i,r);
                int dif=max-min;
                dif-=a[i];
                maxDiff=Math.max(maxDiff,dif);
            }
            out.println(maxDiff);
        }
        out.close();
    }
    public static void createArrayMin(int a[],int n)
    {
        int m=(int)(Math.log(n+1)/Math.log(2));
        for(int i=0;i<=n;i++)
        {
            minArr[i][0]=a[i];
        }
        for(int j=1;j<30;j++)
        {
            for(int i=0;i<=n;i++)
            {
                int s=(int)Math.pow(2,j);
                int last=i+s-1;
                if(last<=n)
                {
                    int p1=i;
                    int p2=i+(s/2);
                    int val=Math.min(minArr[p1][j-1],minArr[p2][j-1]);
                    minArr[i][j]=val;
                }
            }
        }
    }
    public static int getMin(int x,int y)
    {
        int len=y-x+1;
        int min=Integer.MAX_VALUE;
        while(len>0)
        {
            int q=(int)(Math.log(len)/Math.log(2));
            min=Math.min(min,minArr[x][q]);
            q=(int)Math.pow(2,q);
            x+=q;
            len-=q;
        }
        return min;
    }
    public static void createArrayMax(int a[],int n)
    {
        int m=(int)(Math.log(n+1)/Math.log(2));
        for(int i=0;i<=n;i++)
        {
            maxArr[i][0]=a[i];
        }
        for(int j=1;j<30;j++)
        {
            for(int i=0;i<=n;i++)
            {
                int s=(int)Math.pow(2,j);
                int last=i+s-1;
                if(last<=n)
                {
                    int p1=i;
                    int p2=i+(s/2);
                    int val=Math.max(maxArr[p1][j-1],maxArr[p2][j-1]);
                    maxArr[i][j]=val;
                }
            }
        }
    }
    public static int getMax(int x,int y)
    {
        int len=y-x+1;
        int max=Integer.MIN_VALUE;
        while(len>0)
        {
            int q=(int)(Math.log(len)/Math.log(2));
            max=Math.max(max,maxArr[x][q]);
            q=(int)Math.pow(2,q);
            x+=q;
            len-=q;
        }
        return max;
    }
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;
        public FastReader()
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt()
        {
            return Integer.parseInt(next());
        }
        long nextLong()
        {
            return Long.parseLong(next());
        }
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
        String nextLine()
        {
            String str="";
            try
            {
                str=br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}