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.*;
import java.math.*;
import java.math.BigInteger;


public final class A
{    
	static PrintWriter out = new PrintWriter(System.out); 
	static StringBuilder ans=new StringBuilder();
	static FastReader in=new FastReader();
	static ArrayList<ArrayList<Integer>> g;
	static long mod=(long)1e9+7,INF=Long.MAX_VALUE;
	static boolean set[],col[]; 
	static int par[],tot[],partial[];
	static int D[],P[][];
	static long dp[][],max=0;
	static long seg[];
	//static pair moves[]= {new pair(-1,0),new pair(1,0), new pair(0,-1), new pair(0,1)};
	public static void main(String args[])throws IOException
	{				

		int N=i();
		int A[]=input(N);
		int ans=0;
		for(int m=30; m>=1; m--)
		{
			int max=0,s=0;
			for(int i=0; i<N; i++)
			{
				max=Math.max(max,A[i]);
				s=Math.max(A[i],s+A[i]);
				if(max==m)
				{
					//System.out.println("for--> "+ m+" "+ i);
					ans=Math.max(ans, s-m);
				}
				if(max>m)
				{
					s=0;
					max=0;
				}
				
			}
		}
		out.println(ans);
		out.close();
	}
	static long f(long x,long max,long s)
	{
		long l=-1,r=(x/s)+1;
		while(r-l>1)
		{
			long m=(l+r)/2;
			if(x-m*s>max)l=m;
			else r=m;
		}
		return l+1;
	}
	static int f(long A[],long x)
	{
		int l=-1,r=A.length;
		while(r-l>1)
		{
			int m=(l+r)/2;
			if(A[m]>=x)r=m;
			else l=m;			
		}
		return r;
	}
	static void build(int v,int tl,int tr,long A[])
	{
		if(tl==tr)
		{
			seg[v]=A[tl];
			return;
		}
		int tm=(tl+tr)/2;
		build(v*2,tl,tm,A);
		build(v*2+1,tm+1,tr,A);
		seg[v]=GCD(seg[v*2],seg[v*2+1]);
	}
	static long ask(int v,int tl,int tr,int l,int r)
	{
		if(tl==l && tr==r)return seg[v];
		int tm=(tl+tr)/2;
		if(r<=tm)
		{
			return ask(v*2,tl,tm,l,r);
		}
		else if(l>tm)
		{
			return ask(v*2+1,tm+1,tr,l,r);
		}
		else
		{
			return GCD(ask(v*2,tl,tm,l,tm),ask(v*2+1,tm+1,tr,tm+1,r));
		}
	}

	static int bin(int x,ArrayList<Integer> A)
	{
		int l=0,r=A.size()-1;
		while(l<=r)
		{
			int m=(l+r)/2;
			int a=A.get(m);
			if(a==x)return m;
			if(a<x)l=m+1;
			else r=m-1;
		}
		return 0;
	}
	static int left(int x,ArrayList<Integer> A)
	{
		int l=-1,r=A.size();
		while(r-l>1)
		{
			int m=(l+r)/2;
			int a=A.get(m);
			if(a<=x)l=m;
			else r=m;
		}
		return l;
	}
	static int right(int x,ArrayList<Integer> A)
	{
		int l=-1,r=A.size();
		while(r-l>1)
		{
			int m=(l+r)/2;
			int a=A.get(m);
			if(a<x)l=m;
			else r=m;
		}
		return r;
	}



	static boolean equal(long A[],long B[])
	{
		for(int i=0; i<A.length; i++)if(A[i]!=B[i])return false;
		return true;	
	}
	static int lower(long A[],long x)
	{
		int l=-1,r=A.length;
		while(r-l>1)
		{
			int m=(l+r)/2;
			if(A[m]>=x)r=m;
			else l=m;				
		}
		return r;
	}
	static int upper(long A[],long x)
	{
		int l=-1,r=A.length;
		while(r-l>1)
		{
			int m=(l+r)/2;
			if(A[m]<=x)l=m;
			else r=m;
		}
		return l;
	}

	static int max(int a ,int b,int c,int d)
	{
		a=Math.max(a, b);
		c=Math.max(c,d);
		return Math.max(a, c);
	}
	static int min(int a ,int b,int c,int d)
	{
		a=Math.min(a, b);
		c=Math.min(c,d);
		return Math.min(a, c);
	}

	static int find(int l,int r,long A[] ,long val)
	{
		int m=0;
		while(l<=r)
		{
			m=(l+r)/2;
			if(A[m]>=val)r=m-1;
			else l=m+1;
		}
		return m;
	}

	static HashMap<Integer,Integer> Hash(int A[])
	{
		HashMap<Integer,Integer> mp=new HashMap<>();
		for(int a:A)
		{
			int f=mp.getOrDefault(a,0)+1;
			mp.put(a, f);
		}
		return mp;
	}
	static long mul(long a, long b)
	{
		return ( a %mod * 1L * b%mod )%mod;
	}
	static void swap(int A[],int a,int b)
	{
		int t=A[a];
		A[a]=A[b];
		A[b]=t;
	}


	static int find(int a)
	{
		if(par[a]<0)return a;
		return par[a]=find(par[a]);
	}
	static void union(int a,int b)
	{
		a=find(a);
		b=find(b);
		if(a!=b)
		{
			par[a]+=par[b];
			par[b]=a;
		}
	}
	static boolean isSorted(int A[])
	{
		for(int i=1; i<A.length; i++)
		{
			if(A[i]<A[i-1])return false;
		}
		return true;
	}

	static boolean isDivisible(StringBuilder X,int i,long num)
	{
		long r=0;
		for(; i<X.length(); i++)
		{
			r=r*10+(X.charAt(i)-'0');
			r=r%num;
		}
		return r==0;
	}    



	static int lower_Bound(int A[],int low,int high, int x) 
	{ 
		if (low > high) 
			if (x >= A[high]) 
				return A[high]; 

		int mid = (low + high) / 2; 

		if (A[mid] == x) 
			return A[mid]; 

		if (mid > 0 && A[mid - 1] <= x && x < A[mid]) 
			return A[mid - 1]; 

		if (x < A[mid]) 
			return lower_Bound( A, low, mid - 1, x); 

		return lower_Bound(A, mid + 1, high, x); 
	} 

	static String f(String A)
	{
		String X="";
		for(int i=A.length()-1; i>=0; i--)
		{
			int c=A.charAt(i)-'0';
			X+=(c+1)%2;
		}
		return X;
	}

	static void sort(long[] a) //check for long
	{
		ArrayList<Long> l=new ArrayList<>();
		for (long i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}

	static String swap(String X,int i,int j)
	{
		char ch[]=X.toCharArray();
		char a=ch[i];
		ch[i]=ch[j];
		ch[j]=a;
		return new String(ch);
	}

	static int sD(long n)  
	{  

		if (n % 2 == 0 )  
			return 2;  

		for (int i = 3; i * i <= n; i += 2) {  
			if (n % i == 0 )  
				return i;  
		}  

		return (int)n;  
	}  

	static void setGraph(int N)
	{
		tot=new int[N+1];
		partial=new int[N+1];
		D=new int[N+1];
		P=new int[N+1][(int)(Math.log(N)+10)];
		set=new boolean[N+1];
		g=new ArrayList<ArrayList<Integer>>();
		for(int i=0; i<=N; i++)
		{

			g.add(new ArrayList<>());		
			D[i]=0;
			//D2[i]=INF;
		}
	}



	static  long pow(long a,long b)
	{
		//long mod=1000000007;
		long pow=1;
		long x=a;
		while(b!=0)
		{
			if((b&1)!=0)pow=(pow*x)%mod;
			x=(x*x)%mod;
			b/=2;
		}
		return pow;
	}

	static long toggleBits(long x)//one's complement || Toggle bits
	{
		int n=(int)(Math.floor(Math.log(x)/Math.log(2)))+1;

		return ((1<<n)-1)^x;
	}

	static int countBits(long a)
	{
		return (int)(Math.log(a)/Math.log(2)+1);
	}

	static long fact(long N)
	{ 
		long n=2; 
		if(N<=1)return 1;
		else
		{
			for(int i=3; i<=N; i++)n=(n*i)%mod;
		}
		return n;
	}

	static int kadane(int A[])
	{
		int lsum=A[0],gsum=A[0];
		for(int i=1; i<A.length; i++)
		{
			lsum=Math.max(lsum+A[i],A[i]);
			gsum=Math.max(gsum,lsum);
		}
		return gsum;
	}

	static void sort(int[] a) {
		ArrayList<Integer> l=new ArrayList<>();
		for (int i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}

	static boolean isPrime(long N)
	{
		if (N<=1)  return false; 
		if (N<=3)  return true; 
		if (N%2 == 0 || N%3 == 0) return false; 
		for (int i=5; i*i<=N; i=i+6) 
			if (N%i == 0 || N%(i+2) == 0) 
				return false; 
		return true; 
	}
	static void print(char A[])
	{
		for(char c:A)System.out.print(c+" ");
		System.out.println();
	}
	static void print(boolean A[])
	{
		for(boolean c:A)System.out.print(c+" ");
		System.out.println();
	}
	static void print(int A[])
	{
		for(int a:A)System.out.print(a+" ");
		System.out.println();	
	}
	static void print(long A[])
	{
		for(long i:A)System.out.print(i+ " ");
		System.out.println();

	}
	static void print(ArrayList<Integer> A)
	{
		for(int a:A)System.out.print(a+" ");
		System.out.println();
	}

	static int i()
	{
		return in.nextInt();
	}

	static long l()
	{
		return in.nextLong();
	}

	static int[] input(int N){
		int A[]=new int[N];
		for(int i=0; i<N; i++)
		{
			A[i]=in.nextInt();
		}
		return A;
	}

	static long[] inputLong(int N)     {
		long A[]=new long[N];
		for(int i=0; i<A.length; i++)A[i]=in.nextLong();
		return A;
	}

	static long GCD(long a,long b) 
	{
		if(b==0)
		{
			return a;
		}
		else return GCD(b,a%b );
	}

}
class edge 
{
	int s,max;
	edge(int s,int max)
	{
		this.s=s;
		this.max=max;
	}
}


//Code For FastReader
//Code For FastReader
//Code For FastReader
//Code For FastReader
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;
	}

}