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.lang.reflect.Array;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main
{	
   static long mod=(long)(1e+9 + 7);
	
   //static long mod=(long)998244353;
   static int[] sieve;
   static ArrayList<Integer> primes;
   static PrintWriter out;
   static fast s;
   static StringBuilder fans;
   
   static int x_dir[];
   static int y_dir[];

   static Tree tree[];
   static int a[];
   
   static class Tree
   {
   	long suffix;
   	long prefix;
   	long sum;
   	long max;
   	
   	public Tree()
   	{
   		this.suffix=this.prefix=this.sum=this.max=Integer.MIN_VALUE;
   	}	
   	public Tree(long val)
   	{
   		this.suffix=this.prefix=this.sum=this.max=val;
   	}	
   	public void setval(long val)
   	{
   		this.suffix=this.prefix=this.sum=this.max=val;
   	}
   	public void merge(Tree left,Tree right)
   	{
   		this.sum=left.sum+right.sum;
   		this.prefix=Math.max(left.prefix, left.sum+right.prefix);
   		this.suffix=Math.max(right.suffix, right.sum+left.suffix);
   		this.max=Math.max(Math.max(left.sum, right.sum),left.suffix+right.prefix);
   	}	
   }
   	
   	////////////////////////////////////Functions///////////////////////////////////////////
   	
   	public static void build(int n,int start,int end,int size)
      {
   	   int mid=(start+end)>>1;
   	   
   	   if(start==end && start>size) 
   	   {
   		   tree[n]=new Tree();
   		   return;
   	   }
   	   if(start==end)
   	   {
   		   tree[n]=new Tree(a[start]);
   		   return;
   	   }
   	   
   	   build(n<<1,start,mid,size);
   	   build((n<<1) + 1,mid+1,end,size);
   	   
   	   tree[n]=new Tree();
   	   tree[n].merge(tree[n<<1], tree[(n<<1) + 1]);
      }
      
      public static Tree query(int n,int start,int end,int l ,int r)
      {
   	   int mid=(start+end)>>1;
   	   
   	   if(start >=l && end<=r) return tree[n];
   	   else if(start > r || end<l) return null;
   	   
   	   Tree left=null, right=null;
   	   
   	   if(l<=mid) 
   		   left=query(n<<1,start,mid,l,r);
   	   if(r>mid)
   		   right=query((n<<1) + 1,mid+1,end,l,r);
   	   
   	   if(left==null) return right;
   	   if(right==null) return left;
   	   
   	   Tree t=new Tree();
   	   t.merge(left, right);
   	   
   	   return t;
      }
      
   public static void solve()
   {
   	int n=s.nextInt();
   	a=new int[n+1];
   	for(int i=1;i<=n;i++) a[i]=s.nextInt();
   	
      HashMap<Integer,Integer> left=new HashMap<Integer,Integer>();
      HashMap<Integer,Integer> right=new HashMap<Integer,Integer>();
      
      int left_ind[]=new int[n+1];
      int right_ind[]=new int[n+1];
      
      Arrays.fill(right_ind, n);
      Arrays.fill(left_ind, 1);
      
      for(int i=1;i<=n;i++)
      	{
      		int cur=a[i];
      		for(int j=30;j>a[i];j--)
      			{
      				if(left.containsKey(j))
      					left_ind[i]=Math.max(left_ind[i], left.get(j)+1);
      			}
      		left.put(cur,i);
      	}
      
      for(int i=n;i>=1;i--)
      	{
      		int cur=a[i];
      		for(int j=30;j>a[i];j--)
      			{
      				if(right.containsKey(j))
      					right_ind[i]=Math.min(right_ind[i], right.get(j)-1);
      			}
      		right.put(cur,i);
      	}
      
      //Segment
      int max=4*n;
      tree=new Tree[max+5];
      
      build(1,1,n,max);
      int ans=Integer.MIN_VALUE;
      
      for(int i=1;i<=n;i++)
      	{
      		int left_border=left_ind[i];
      		int right_border=right_ind[i];
      		
      		int right_sum=(int)query(1,1,n,i,right_border).prefix;
      		int left_sum=0;
      		if(left_border<i) left_sum=(int)query(1,1,n,left_border,i-1).suffix;
      		
      		int sum=Math.max(Math.max(left_sum+right_sum,a[i]),Math.max(right_sum, (int)query(1,1,n,left_border,i).suffix));
      		//System.out.println(i+" "+left_border+" "+right_border+" "+left_sum+" "+right_sum);
      		sum-=a[i];
      		ans=Math.max(ans, sum);
      	}
      fans.append(ans+"\n");
   }
   
   public static void main(String[] args) throws java.lang.Exception
   {	  	
	     s = new fast();
	     
	     out=new PrintWriter(System.out);
	     fans=new StringBuilder("");
		  
	     int t=1;
	     
	     while(t>0)
	    	 {
	    		 solve();
	    		 t--;
	    	 }
	    
	    out.println(fans);
	    out.close();
   }
  
 
 
static class fast {   
	
	   private InputStream i;
		private byte[]  buf = new byte[1024];
		private int curChar;
		
		private int numChars;
		
		//Return floor log2n
		public static long log2(long bits) // returns 0 for bits=0
			{
			    int log = 0;
			    if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; }
			    if( bits >= 256 ) { bits >>>= 8; log += 8; }
			    if( bits >= 16  ) { bits >>>= 4; log += 4; }
			    if( bits >= 4   ) { bits >>>= 2; log += 2; }
			    return log + ( bits >>> 1 );
			}
		
		public static boolean next_permutation(int a[])
		   {
			   int i=0,j=0;int index=-1;	   
			   int n=a.length;
			   
			   for(i=0;i<n-1;i++)
				   if(a[i]<a[i+1]) index=i;
			   
			   if(index==-1) return false;
			   i=index;
 
			  
			   for(j=i+1;j<n && a[i]<a[j];j++);
 
			   int temp=a[i];
			   a[i]=a[j-1];
			   a[j-1]=temp;
			   	   
			   for(int p=i+1,q=n-1;p<q;p++,q--)
			   {
				   temp=a[p];
				   a[p]=a[q];
				   a[q]=temp;
			   }
			   
			   return true;
		   }
		   
		public static void sieve(int size)
		{
			sieve=new int[size+1];
			
			primes=new ArrayList<Integer>();
			
			sieve[1]=1;
			
			for(int i=2;i*i<=size;i++)
			{
				if(sieve[i]==0)
				 {
					for(int j=i*i;j<size;j+=i) {sieve[j]=1;}
				 }
			}
			
			for(int i=2;i<=size;i++)
			{
				if(sieve[i]==0) primes.add(i);
			}
		}
		
		public static long pow(long a, long p){
		    long o = 1;
		    for(; p>0; p>>=1){
		        if((p&1)==1)o = mul(o, a);
		        a = mul(a, a);
		    }
		    return o;
		}
		
		public static long add(long... a){
		    long o = 0;
		    for(long x:a)o = (o+mod+x)%mod;
		    return o;
		}
		
		public static long mul(long... a){
		    long p = 1;
		    for(long x:a)p = (mod+(p*x)%mod)%mod;
		    return p;
		}
		
		public static long mod_inv(long n)
		{
			return pow(n,mod-2);
		}
		   
		public long gcd(long r,long ans)
		{
			if(r==0) return ans;
			return gcd(ans%r,r);
		}
		
		public fast() {
			this(System.in);
		}
		public fast(InputStream is) {
			i = is;
		}
		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = i.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 nextString() {
     		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 nextLong() {
			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 nextInt() {
			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 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;
		}
 
	}	
}