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.*;

public class D {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt();
		int[] a = new int[n + 1];
		for (int i = 1; i <= n; i++)
			a[i] = sc.nextInt();
		int[] prefix = new int[n + 1];
		for (int i = 1; i <= n; i++)
			prefix[i] = prefix[i - 1] + a[i];
		SparseTable min = new SparseTable(prefix, true);
		SparseTable max = new SparseTable(prefix, false);
		Stack<Integer> stack = new Stack();
		int[] left = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			while (!stack.isEmpty() && a[i] >= a[stack.peek()])
				stack.pop();
			left[i] = stack.isEmpty() ? -1 : stack.peek();
			stack.push(i);

		}
		stack.clear();
		int[] right = new int[n + 1];
		for (int i = n; i > 0; i--) {
			while (!stack.isEmpty() && a[i] >= a[stack.peek()])
				stack.pop();
			right[i] = stack.isEmpty() ? -1 : stack.peek();
			stack.push(i);

		}
		long ans = -(long) 1e9;
		for (int i = 1; i <= n; i++) {
			long r = max.query(i, right[i] == -1 ? n : (right[i] - 1));
			long l = min.query(left[i] == -1 ? 0 : left[i], i - 1);
//			System.out.println(left[i]+" "+right[i]);
			ans = Math.max(ans, r - l - a[i]);
		}
		out.println(ans);

		out.close();

	}

	static class SparseTable {
		// table [i][j] = the index with the min value from a[j] to
		// a[j+(1<<i)-1];

		int[] a, log, table[];
		boolean min;

		SparseTable(int[] b, boolean min) {
			this.a = b.clone();

			this.min = min;
			if (!min) {
				for (int i = 0; i < a.length; i++)
					a[i] *= -1;
			}
			int n = a.length;
			log = new int[n + 1];
			for (int i = 2; i <= n; i++)
				log[i] = log[i / 2] + 1;
			table = new int[log[n] + 1][n];
			for (int i = 0; i < n; i++)
				table[0][i] = i;
			for (int i = 1, len = 2; len <= n; i++, len <<= 1)
				for (int j = 0; j + len <= n; j++) {
					int u = table[i - 1][j], v = table[i - 1][j + len / 2];
					table[i][j] = a[u] < a[v] ? u : v;
				}

		}

		int query(int l, int r) {
			int len = r - l + 1;
			int lg = log[len];
			int u = table[lg][l];
			int v = table[lg][r - (1 << lg) + 1];
			int bestIdx = a[u] < a[v] ? u : v;
			return min ? a[bestIdx] : -a[bestIdx]; // return a[bestIdx] for value
		}

	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		Scanner(String fileName) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(fileName));
		}

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

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

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

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

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

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

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

	}

	static void sort(int[] a) {
		shuffle(a);
		Arrays.sort(a);
	}

	static void shuffle(int[] a) {
		int n = a.length;
		Random rand = new Random();
		for (int i = 0; i < n; i++) {
			int tmpIdx = rand.nextInt(n);
			int tmp = a[i];
			a[i] = a[tmpIdx];
			a[tmpIdx] = tmp;
		}
	}

}