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




public class Main {
	

	public static class FastReader {
		BufferedReader br;
		StringTokenizer root;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (root == null || !root.hasMoreTokens()) {
				try {
					root = new StringTokenizer(br.readLine());
				} catch (Exception addd) {
					addd.printStackTrace();
				}
			}
			return root.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception addd) {
				addd.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	
	public static FastReader sc = new FastReader();
 
	static int mod = (int) (1e9+7),MAX=(int) (2e5);
    static List<Integer>[] edges;
    
	public static void main(String[] args){
      
	  int n = sc.nextInt();
	  int[] a = new int[n];
	  for(int i=0;i<n;++i) a[i] = sc.nextInt();
	  
	  long[] p = pref(a);
	  long[] s = suff(a);
	  int[] right = nge(a,n);
	  int[] left = pge(a,n);
	  
	  SegmentTree pref = new SegmentTree(p,n);
	  SegmentTree suff = new SegmentTree(s,n);

	  long max = Integer.MIN_VALUE;
	  for(int i=0;i<n;++i) {
		  int l = left[i]+1;
		  int r = right[i]-1;
		
		  long ll=0,rr=0;
		  if(i-1 >= 0 && l <= i-1) ll = Math.max(0,suff.query(s, l, i-1) - s[i]);
		  if(i+1 < n && i+1 <= r) rr = Math.max(0,pref.query(p, i+1, r) - p[i]);
		  
		  max = Math.max(max,ll+rr);
	  }
	  out.print(max);
	 
      out.close();
	}
	
	
	public static class SegmentTree 
	{ 
		long seg[];  
 
		SegmentTree(long[] a, int n) { 
			seg = new long[4*n];
			buildTree(a,0,n-1,1);
		} 
		
		public void buildTree(long[] a, int start, int end, int i) {
			if(start == end) {
				seg[i] = a[start];
				return;
			}
			int mid = start +(end-start)/2;
			buildTree(a,start,mid,2*i);
			buildTree(a,mid+1,end,2*i+1);
			
			seg[i] = Math.max(seg[2*i] , seg[2*i+1]);
			
		}
 
		public long query(long[] a, int l,int r) {
			return query(0,a.length-1,1,l,r);
		}
		
		public long query(long m, long mid2, int i, int l, int r) {
			// OUTSIDE
			if(m>r || mid2<l)
				return Integer.MIN_VALUE; // depend on q
			//INSIDE
			if(m>=l && mid2<=r)
				return seg[i];
			// PARTIAL
			long mid = m+(mid2-m)/2;
			long ansl = query(m,mid,2*i,l,r);
			long ansr = query(mid+1,mid2,2*i+1,l,r);
			
			return Math.max(ansl,ansr);
			
		}
 
		public void update(long[] a,int idx,long ans) {
			updateTree(a,0,a.length-1,1,idx,ans);
		}
		public void updateTree(long[] a,int start, int end, int i, int idx, long ans) {
			if(start == end) {
				a[idx] = ans;
				seg[i] = ans;
				return;
			}
			
			int mid = start+(end-start)/2;
			if(idx>mid)
				updateTree(a,mid+1,end,2*i+1,idx,ans);
			else updateTree(a,start,mid,2*i,idx,ans);
			
			seg[i] = Math.max(seg[2*i], seg[2*i+1]);
			
		}
 
	}

	 static void rev(int arr[]){
		 int start=0, end=arr.length;
	        int temp; 
	        while (start < end) { 
	            temp = arr[start]; 
	            arr[start] = arr[end]; 
	            arr[end] = temp; 
	            start++; 
	            end--; 
	        } 
	    } 
	 
	 static int[] nge(int arr[], int n){  
		 /*
		  * return indices( 0 based ) of Next greater elements 
		  */
		    Stack<Integer> s = new Stack<Integer>();  
		    int arr1[] = new int[n];
		    for (int i = n - 1; i >= 0; i--){  
		        while (!s.isEmpty() && arr[s.peek()] <= arr[i]) s.pop();  
		        if (s.empty()) arr1[i] = n; // or -1 to show No nge          
		        else arr1[i] = s.peek();          
		        s.push(i);  
		    }  
		  return arr1;
	}  
	 
	 static int[] pge(int arr[],int n) {
		 /*
		  * return indices( 0 based ) of Previous greater elements 
		  */
		 int[] ans = new int[n];
		 int ptr = 0;
		 Stack<Integer> s = new Stack<>();
		 s.push(0);
		 ans[ptr++] = -1; // for first No pge is present
		 for(int i=1;i<n;++i) {
			 while(s.size() > 0 && arr[s.peek()] < arr[i]) s.pop();
			 if(s.size() == 0) ans[ptr++] = -1;
			 else ans[ptr++] = s.peek();
			 s.push(i);
		 }
		 return ans;
	 }
	 
	 static long[] pref(int[] a) {
		 int n = a.length;
		 long[] pre = new long[n];
		 pre[0] = a[0];
		 for(int i=1;i<n;++i) pre[i] = pre[i-1] + a[i];
		 return pre;
	 }
	 
	 static long[] suff(int[] a) {
		 int n = a.length;
		 long[] suff = new long[n];
		 suff[n-1] = a[n-1];
		 for(int i=n-2;i>=0;--i) suff[i] = suff[i+1] + a[i];
		 return suff;
	 }
	

}
