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.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;


public class Educational88 {

	
	static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public Reader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[64]; // line length
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}

	public static long[] initArray(int n, Reader scan) throws IOException {

		long arr[] = new long[n];
		for (int i = 0; i < n; i++) {
			arr[i] = scan.nextLong();
		}

		return arr;
	}

	public static long sum(long arr[]) {

		long sum = 0;
		for (long i : arr) {
			sum += (long) i;
		}

		return sum;
	}

	public static long max(long arr[]) {

		long max = Long.MIN_VALUE;

		for (long i : arr) {
			max = Math.max(i, max);
		}

		return max;
	}

	public static long min(long arr[]) {
		long min = Long.MAX_VALUE;

		for (long i : arr) {
			min = Math.min(i, min);
		}

		return min;
	}
	
	public static List<Integer>[] initAdjacency(int n, Reader scan, boolean type) throws IOException{
		
		List<Integer> adj[]=new ArrayList[n];
		
		
		for(int i=0;i<n;i++) {
			int u=scan.nextInt();
			int v=scan.nextInt();
			
			if(adj[u]==null) adj[u]=new ArrayList<>();
			if(type&&adj[v]==null) adj[v]=new ArrayList<>();
			
			adj[u].add(v);
			
			if(type) adj[v].add(u);
			
		}
		
		return adj;
	}
	public static void main(String[] args) throws IOException {
		
		Reader scan=new Reader();
		int t=1;
		while(t-->0) {
			int n=scan.nextInt();
			long arr[]=initArray(n, scan);
			System.out.println(D(n, arr));
		}
	}
	
	public static int A(int n, int m, int k) {
		
		int val=n/k;
		
		if(m<=val) {
			return m;
		}
		
		int rem= m-val;
		
		int max= (int)Math.ceil((double)(rem)/(k-1));
		
		return val-max;
		
	}
	
	public static long B(String arr[], int n, int m, long x, long y) {
		
		
		long ans=0;
		for(int i=0;i<n;i++) {
			
			int last=-1;
			int j=0;
			
			while(j<m) {
				
				if(arr[i].charAt(j)=='*') {
					
					ans+= BHelper(j-last-1, x, y);
					last=j;
				}
				
				j++;
				
			}
			
			ans+= BHelper(j-last-1, x, y);
			
		}
		
		return ans;
		
	}
	
	public static long BHelper(int len, long x, long y) {
		
		
		
		long cost1= len*x;
		long cost2= (len/2)*y+ (len%2)*x;
		
		return Math.min(cost1,  cost2);
		
		
	}
	
	public static long C(long h, long c, long t) {
		
		
		
		if((h+c)>=2*t) {
			return 2;
		}
		
		
		if(t>=h) return 1;
		
		long x= Math.abs((t-h)/(h+c-2*t));
		System.out.println("x="+x);
		
		System.out.println(2*x+1);
		System.out.println(2*x+3);
		
		//System.out.println(low+" "+high);
		
		double val1= (double)((double)x*c)/((long)2*x+(long)1)+ (double)((double)(x+1)*h)/((long)2*x+(long)1);

		double val2= (double)((double)(x+1)*c)/((long)2*x+(long)3)+ (double)((double)(x+2)*h)/((long)2*x+(long)3);
		
		System.out.println("val1="+val1);
		System.out.println("val2="+val2);
		
		double diff1= Math.abs((double)t-val1);
		double diff2= Math.abs((double)t-val2);
		double diff3= Math.abs((double)(t-((double)(h+c)/(double)2)));
		
		System.out.println(diff1+"-");
		System.out.println(diff2+"-");
		System.out.println(diff3+"-");
		
		double min= Math.min(diff1,  Math.min(diff2, diff3));
		//System.out.println("min="+min);
		
		if(diff3==min) {
			return 2;
		}
		
		if(diff1==min) {
			return 2*x+1;
		}
		
		if(diff2==min) {
			return 2*x+3;
		}
		
		return 2;
		
	}
	
	public static long D(int n, long arr[]) {
		
		
		int nextGreat[]=new int[n];
		int preGreat[]=new int[n];
		
		Stack<Integer> stack=new Stack<>();
		
		for(int i=0;i<n;i++) {
			
			while(!stack.isEmpty()) {
				if(arr[i]<=arr[stack.peek()]) {
					break;
				}else {
					nextGreat[stack.pop()]= i;
				}
			}
			
			stack.push(i);
		}
		
		while(!stack.isEmpty()) {
			nextGreat[stack.pop()]=n;
		}
		
		for(int i=n-1;i>=0;i--) {
			
			while(!stack.isEmpty()) {
				if(arr[i]<=arr[stack.peek()]) {
					break;
				}else {
					preGreat[stack.pop()]= i;
				}
			}
			
			stack.push(i);
		}
		
		while(!stack.isEmpty()) {
			preGreat[stack.pop()]=-1;
		}
		
		long preSum[]=new long[n+1];
		
		for(int i=1;i<=n;i++) {
			preSum[i]= preSum[i-1]+arr[i-1];
		}
		
		Range range=new Range(preSum);
		
		long ans=0;
		
		for(int i=0;i<n;i++) {
			
//			System.out.println("For i= "+i);
			
			int pre= preGreat[i];
			int next= nextGreat[i];
			
//			System.out.println(pre+" "+next);
			
			long max= range.getMax(i+1, next);
			long min= range.getMin(pre+1, i);
			
//			System.out.println("MAX= "+ max+" min= "+ min);
//			
//			System.out.println("For i= "+ i+" ans is "+ (max-min-arr[i]));
			
			ans=Math.max(ans,  max-min-arr[i]);
			
		}
		
		return ans;
		
		
		
	}
	
	public static long E(long n, long k) {
		
		long mod=998244353;
		
		long fact[]=new long[500000];
		long factInv[]=new long[500000];
		
		fact[0]=1;
		for(int i=1;i<500000;i++) {
			fact[i]=i*fact[i-1];
			fact[i]%=mod;
		}
		
//		for(int i=0;i<=10;i++) {
//			System.out.print(fact[i]+" ");
//		}
		
		for(int i=0;i<500000;i++) {
			factInv[i]= BigInteger.valueOf(fact[i]).modInverse(BigInteger.valueOf(998244353)).longValue();
		}
		
//		for(int i=0;i<=10;i++) {
//			System.out.print(factInv[i]+" ");
//		}
//		System.out.println();
		
		long ans=0;
		for(int i=1;;i++) {
			
			long count= n/i-1;
			
//			System.out.println("count for i="+i+" = " +count);
			
			if(count>=(k-1)) {
				ans+= (((fact[(int)count]*factInv[(int)count-(int)k+1])%mod)*(factInv[(int)k-1]))%mod;
				ans%=mod;
//				System.out.println("ans is "+ans);
			}else {
				break;
			}
			
		}
		
		return ans;
		
	}
	
	public static long calFact(long k) {
		
		long mod=998244353;
		long ans=1;
		for(long i=1;i<=k;i++) {
			ans*=i;
			ans%=mod;
		}
		
		return ans;
	}

}

class Range{
	
	public long rangeMax[][];
	public long rangeMin[][];
	
	public Range(long arr[]) {
		
		
		double hi= Math.ceil(Math.log(arr.length)/Math.log(2));
		//System.out.println("hi="+hi);
		rangeMax=new long[arr.length][(int)hi+1];
		rangeMin=new long[arr.length][(int)hi+1];
		
		for(int i=0;i<arr.length;i++) {
			rangeMax[i][0]=arr[i];
			rangeMin[i][0]=arr[i];
		}
		
		for(int len=2, j=1;len<=arr.length;len*=2, j++) {
			
			for(int i=0;i<arr.length;i++) {
				
				if(i+len/2>=arr.length) {
					rangeMax[i][j]=rangeMax[i][j-1];
					rangeMin[i][j]=rangeMin[i][j-1];
					continue;
				}
				rangeMax[i][j]= Math.max(rangeMax[i][j-1], rangeMax[i+len/2][j-1]);
				rangeMin[i][j]= Math.min(rangeMin[i][j-1], rangeMin[i+len/2][j-1]);
				
			}
			
		}
		
	}
	
	
	public long getMax(int l, int r) {
		
		
		int len= r-l+1;
		long ans=Long.MIN_VALUE;
		int cur=l;
		while(len!=0) {
			int val=(int)(Math.log(len)/Math.log(2));
			len-= (1<<val);
			ans= Math.max(ans,  rangeMax[cur][val]);
			cur+= (1<<val);
		}
		
		return ans;
		
	}
	
	public long getMin(int l, int r) {
		
		int len= r-l+1;
		long ans=Long.MAX_VALUE;
		int cur=l;
		while(len!=0) {
			int val=(int)(Math.log(len)/Math.log(2));
			len-= (1<<val);
			ans= Math.min(ans,  rangeMin[cur][val]);
			cur+= (1<<val);
		}
		
		return ans;
	}
	
	
}
