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 d {
	static final FS sc = new FS();
	static final PrintWriter pw = new PrintWriter(System.out);

	static final int maxv = 30;

	static int n;
	static int[] arr, pre;
	static int[][] prev, next;
	public static void main(String[] args) {
		n = sc.nextInt();
		arr = new int[n];
		pre = new int[n];
		node seg = new node(0, n - 1);
		for(int i = 0; i < n; ++i) {
			pre[i] = arr[i] = sc.nextInt();
			if(i > 0) pre[i] += pre[i - 1];
			seg.set(i, pre[i]);
		}

		prev = new int[idx(maxv) + 1][n];
		next = new int[idx(maxv) + 1][n];
		for(int val = -maxv; val <= maxv; ++val) {
			prev[idx(val)][0] = -1;
			next[idx(val)][n - 1] = n;
		}

		for(int i = 0; i < n; ++i) {
			if(i > 0) {
				for(int val = -maxv; val <= maxv; ++val) prev[idx(val)][i] = prev[idx(val)][i - 1];
			}
			prev[idx(arr[i])][i] = i;
		}

		for(int i = n - 1; i >= 0; --i) {
			if(i < n - 1) {
				for(int val = -maxv; val <= maxv; ++val) next[idx(val)][i] = next[idx(val)][i + 1];
			}
			next[idx(arr[i])][i] = i;
		}

		int out = -(Integer.MAX_VALUE / 2);
		for(int i = 0; i < n; ++i) {
			int l = -1, r = n;
			for(int val = arr[i] + 1; val <= maxv; ++val) {
				l = Math.max(l, prev[idx(val)][i]);
				r = Math.min(r, next[idx(val)][i]);
			}

			++l;
			--r;

			int left = 0;
			if(i > 0) {
				if(l > 0) left = seg.getMin(l - 1, i - 1);
				else left = Math.min(0, seg.getMin(0, i - 1));
			}
			int right = seg.getMax(i, r);

			int curr = right - left - arr[i];
			out = Math.max(out, curr);
		}

		pw.println(out);
		pw.flush();
	}
	static int idx(int in) {
		return in + maxv;
	}
	static class node{
		int li, ri, m, min, max;
		node l, r;
		node(int ll, int rr){
			li = ll;
			ri = rr;
			m = (li + ri) / 2;

			min = max = -1;
			if(li != ri) {
				l = new node(li, m);
				r = new node(m + 1, ri);
			}
		}
		void set(int i, int v) {
			if(li == ri) {
				min = max = v;
				return;
			}

			if(i <= m) l.set(i, v);
			else r.set(i, v);

			min = Math.min(l.min, r.min);
			max = Math.max(l.max, r.max);
		}
		int getMin(int s, int e) {
			if(s <= li && ri <= e) return min;

			int out = Integer.MAX_VALUE / 2;
			if(s <= m) out = Math.min(out, l.getMin(s, e));
			if(e > m) out = Math.min(out, r.getMin(s, e));

			return out;
		}
		int getMax(int s, int e) {
			if(s <= li && ri <= e) return max;

			int out = -(Integer.MAX_VALUE / 2);
			if(s <= m) out = Math.max(out, l.getMax(s, e));
			if(e > m) out = Math.max(out, r.getMax(s, e));

			return out;
		}
	}
	static class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		String next() {
			while(!st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(Exception e) {}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
}