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.BufferedReader;
import java.io.InputStreamReader;

public class Sola4 {
	// len using A[i] = MaxSum[A[i]][i-1]+dpleft[A[i][i+1];
	
	public int getMaxSegmentDp(int[] row){
		int len = row.length;
		int[][] dpl = new int[len+1][61];
		int[][] dpr = new int[len+1][61];
		
		for(int j = 0;j< 61;j++){
			dpl[0][j] = 0;
		}
		for(int j =0;j<61;j++){
			dpr[len][j] = 0;
		}
		for(int i = 0;i< len;i++){
			int t = row[i];
			for(int j = -30;j<t;j++){
				int k = j+30;
				dpl[i+1][k]= dpl[i][k];
			}
			for(int j = t;j<=30;j++){
				int k = j+30;
				dpl[i+1][k]= Math.max(dpl[i][k]+t, t);
			}
		}
		for(int i = len-1;i>= 0;i--){
			int t = row[i];
			for(int j = -30;j<t;j++){
				int k = j+30;
				dpr[i][k]= dpr[i+1][k];
			}
			for(int j = t;j<=30;j++){
				int k = j+30;
				dpr[i][k]= Math.max(dpr[i+1][k]+t, t);
			}
		}
		int answer = 0;
		for(int i = 1; i <=len;i++){
			// System.out.println(row[i-1] + "," + dpl[i-1][row[i-1]+30]
//					+ "," + dpr[i][row[i-1]+30]);
			int curr = Math.max(0, dpl[i-1][row[i-1]+30]) + 
					Math.max(0, dpr[i][row[i-1]+30]);
			answer = Math.max(curr, answer);
		}
		return answer;
	}

	public static void main(String[] args)throws Exception{

		Sola4 sd = new Sola4();
		BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));
		String lineNo = obj.readLine();
		lineNo = obj.readLine();
		String[] d = lineNo.split(" ");
		int len = d.length;
		int arr[] = new int[len];
			for(int i = 0; i <len;i++){
				arr[i] = Integer.parseInt(d[i]);
			}
			System.out.println(sd.getMaxSegmentDp(arr));
	}

}
//
/*
package codeforces;	

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Sola4 {
	public int getMaxSegment(int[] row){
	int len = row.length;
	    int outerMax = 0;
		int sumIncludingMax = 0;
		int max = Integer.MIN_VALUE;
		int negativeResidue = 0;
		for(int i = 0;i<len;i++){
			// sum += row[i];
			if(sum == 0 && row[i] <=0)continue;
			if(sum == 0 && row[i] >=0){
				sum = row[i];
				max = row[i];
				continue;
			}
			int prevMax = max;
			if(row[i] < 0){
				negativeResidue += row[i];
				if((sumIncludingMax +row[i]) <= 0){
					// think if we need to remove previous minuses
					//  3 -2 -2 8 9
					outerMax = Math.max(outerMax, sumIncludingMax-prevMax);
					sumIncludingMax = 0;
					negativeResidue = 0;
					max = 0;
				}else{
					if((sumIncludingMax - max +row[i]) <=0 ){
						gonePartialNe = true;
						
					}

					sumIncludingMax += row[i];
				}
			}
			else{
				if(gonePartialNe){
					int newSum = sumIncludingMax + row[i];
					if(max < row[i]){
						sumIncludingMax += row[i];
						max = row[i];
						gonePartialNe = false;
					}else{
					   if((newSum - max )> 0){
						   
					   }else{
						   markIndex = i; // calculate sum till this window
						   newIndex = i;
					   }
					}
				}
				max = Math.max(max, row[i]);
				negativeResidue = 0;
				sumIncludingMax += row[i];
			}
		}
		if(sum >0){
			outerMax = Math.max(outerMax, sum-negativeResidue-max);
		}
		return outerMax;
	}
	
	public static void main(String[] args)throws Exception{

		Sola4 sd = new Sola4();
		BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));
		String lineNo = obj.readLine();
		lineNo = obj.readLine();
		String[] d = lineNo.split(" ");
		int len = d.length;
		int arr[] = new int[len];
			for(int i = 0; i <len;i++){
				arr[i] = Integer.parseInt(d[i]);
			}
			System.out.println(sd.getMaxSegment(arr));
	}

}
*/