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.
// package CodeForces;

import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.util.Stack;

public class EducationalRound88D {
	
	public static class Node {
		long p_max, s_max, total;
		
		public Node(long p_max, long s_max, long total) {
			this.p_max = Long.max(0, p_max);
			this.s_max = Long.max(0, s_max);
			this.total = total;
		}
		
		public Node(Node A, Node B) {
			this.total = A.total + B.total;
			this.p_max = Long.max(0, Long.max(A.p_max, A.total + B.p_max));
			this.s_max = Long.max(0, Long.max(A.s_max + B.total, B.s_max));
		}
	}
	
	public static Node[] tree;
	
	public static void Build(int[] arr, int start, int end, int index) {
		if(start == end) {
			tree[index] = new Node(arr[start], arr[start], arr[start]);
			return;
		}
		int mid = (start + end)>>1;
		Build(arr, start, mid, index<<1);
		Build(arr, mid + 1, end, index<<1|1);
		tree[index] = new Node(tree[index<<1], tree[index<<1|1]);
	}
	
	public static Node Query(int start, int end, int index, int l, int r) {
		if(start > r || l > end) {
			return new Node(0, 0, 0);
		}
		if(l <= start && end <= r) {
			return tree[index];
		}
		int mid = (start + end)>>1;
		return new Node(Query(start, mid, index<<1, l, r), Query(mid + 1, end, index<<1|1, l, r));
	}

	public static void solve() {
		int n = s.nextInt();
		int[] arr = s.nextIntArray(n);
		long[] prefix = new long[n];
		prefix[0] = arr[0];
		for(int i = 1; i < n; i++) {
			prefix[i] = prefix[i - 1] + arr[i];
		}
		tree = new Node[4 * n + 1];
		Build(arr, 0, n - 1, 1);
		Stack<Integer> nge = new Stack<Integer>();
		int[] next_greater = new int[n];
		for(int i = 0; i < n;i++) {
			while(!nge.isEmpty()) {
				int top_ind = nge.peek();
				if(arr[top_ind] < arr[i]) {
					nge.pop();
					next_greater[top_ind] = i - 1;
				}else {
					break;
				}
			}
			nge.push(i);
		}
		while(!nge.isEmpty()) {
			int top_ind = nge.pop();
			next_greater[top_ind] = n - 1;
		}
		int[] prev_greater = new int[n];
		for(int i = n - 1; i >= 0; i--) {
			while(!nge.isEmpty()) {
				int top_ind = nge.peek();
				if(arr[top_ind] < arr[i]) {
					nge.pop();
					prev_greater[top_ind] = i + 1;
				}else {
					break;
				}
			}
			nge.push(i);
		}
		while(!nge.isEmpty()) {
			int top_ind = nge.pop();
			prev_greater[top_ind] = 0;
		}
		long ans = 0;
		for(int i = 0; i < n; i++) {
			int rangel = prev_greater[i], ranger = next_greater[i];
			Node first = i - 1 >= 0? Query(0, n - 1, 1, rangel, i - 1) : new Node(0, 0, 0);
			Node second = i + 1 < n ? Query(0, n - 1, 1, i + 1, ranger) : new Node(0, 0, 0);
			ans = Long.max(first.s_max + second.p_max, ans);
		}
		out.println(ans);
	}

	public static void main(String[] args) {
		new Thread(null, null, "Thread", 1 << 27) {
			public void run() {
				try {
					out = new PrintWriter(new BufferedOutputStream(System.out));
					s = new FastReader(System.in);
					solve();
					out.close();
				} catch (Exception e) {
					e.printStackTrace();
					System.exit(1);
				}
			}
		}.start();
	}

	public static PrintWriter out;
	public static FastReader s;

	public static class FastReader {

		private InputStream stream;
		private byte[] buf = new byte[4096];
		private int curChar, snumChars;

		public FastReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (snumChars == -1) {
				throw new InputMismatchException();
			}
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException E) {
					throw new InputMismatchException();
				}
			}
			if (snumChars <= 0) {
				return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int number = 0;
			do {
				number *= 10;
				number += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			long sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long number = 0;
			do {
				number *= 10L;
				number += (long) (c - '0');
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

		public int[] nextIntArray(int n) {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextInt();
			}
			return arr;
		}

		public long[] nextLongArray(int n) {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextLong();
			}
			return arr;
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndofLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public boolean isEndofLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

	}
	
	
}
