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

public class tr0 {
	static PrintWriter out;
	static StringBuilder sb;
	static int mod = (int) 1e9 + 7;
	static int inf = (int) 1e8;
	static int[] col;
	static int n, m, k;
	static ArrayList<Integer>[] ad;
	static int[][][] memo;
	static ArrayList<Integer> h;
	static char[][] grid;
	static int[] a;
	static boolean f;
	static int offest = 30;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		out = new PrintWriter(System.out);
		n = sc.nextInt();
		a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();
		// System.out.println(Arrays.toString(a));
		memo = new int[n + 1][2][61];
		for (int[][] aa : memo)
			for (int[] al : aa)
				Arrays.fill(al, -1);
//		for (int st = 1; st >= 0; st--) {
//			for (int max = 30; max >= -30; max--) {
//				if (st == 0) {
//					memo[n][st][max + offest] = -inf;
//				} else {
//					memo[n][st][max + offest] = -max;
//				}
//			}
//		}
//		for (int i = n - 1; i >= 0; i--) {
//			for (int st = 1; st >= 0; st--) {
//				for (int max = 30; max >= -30; max--) {
//					int ans = Integer.MIN_VALUE;
//					if (st == 0) {
//						ans = memo[i + 1][st][max + offest];
//						ans = Math.max(ans, a[i] + memo[i + 1][1][a[i] + offest]);
//					}
//					if (st == 1) {
//						ans = Math.max(-max, a[i] + memo[i + 1][st][Math.max(a[i], max) + offest]);
//					}
//					memo[i][st][max + offest] = ans;
//					System.out.println(ans);
//				}
//			}
//		}
//
//		System.out.println(Arrays.toString(memo[0][0]));
//		System.out.println(memo[0][0][30]);
		//for (int i = n - 1; i >= 0; i--)
	//		dp(i, 0, 0);
		System.out.println(dp(0, 0, 0));
		out.flush();
	}

// 0 before,1 in the segment,2 end
	static int dp(int i, int st, int max) {
		if (i == n) {
			if (st == 0) {
				return -inf;
			}
			return -max;
		}
		if (memo[i][st][max + offest] != -1)
			return memo[i][st][max + offest];
		int ans = Integer.MIN_VALUE;
		if (st == 0) {
			ans = dp(i + 1, st, max);
			ans = Math.max(ans, a[i] + dp(i + 1, 1, a[i]));
		}
		if (st == 1) {
			ans = Math.max(-max, a[i] + dp(i + 1, st, Math.max(a[i], max)));
		}
		if (memo[i][st][max + offest] != -1)
			return memo[i][st][max + offest];
		return memo[i][st][max + offest] = ans;
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public int[] nextArrInt(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public long[] nextArrLong(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}