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.*;
public class javaishard{
public static void main(String[] args)
{

   Scanner myObj = new Scanner(System.in);
   int num = Integer.parseInt(myObj.nextLine());
   String[] temp = myObj.nextLine().split(" ");
   int[] arr = new int[num];
   for(int i = 0; i < num; i++)
   {
      arr[i] = Integer.parseInt(temp[i]);
   }
   int[] sums = new int[num+1];
   int sum = 0;
   for(int i = 0; i < num+1; i++)
   {
      sums[i] = sum;
      if(i < num)
      {sum += arr[i];}
   }
   int[] lefts = new int[num];
   int[] rights = new int[num];
   Stack<Integer> stax = new Stack<Integer>();
   for(int i = 0; i < num; i++)
   {
      while(!stax.isEmpty() && arr[stax.peek()] < arr[i])
      {
         rights[stax.pop()] = i;
      }
      stax.push(i);
   }
   while(!stax.isEmpty())
   {
      rights[stax.pop()] = num;
   }
   for(int i = num-1; i >= 0; i--)
   {
      while(!stax.isEmpty() && arr[stax.peek()] < arr[i])
      {
         lefts[stax.pop()] = i+1;
      }
      stax.push(i);
   }
   while(!stax.isEmpty())
   {
      lefts[stax.pop()] = 0;
   }
   
   int jj =(int)( Math.pow(2, Math.ceil(Math.log(num+1)/Math.log(2))));
   int[] maxtree = new int[2*jj-1];
   for(int i = 2*jj-2; i >= 0; i--)
   {
      if(i>=jj-1)
      {
         if(i-(jj-1) < num+1)
         {
            maxtree[i] = sums[i-(jj-1)];
         }
         else
         {
            maxtree[i] = -2147483647;
         }
      }
      else
      {
         maxtree[i] = Math.max(maxtree[2*i+2], maxtree[2*i+1]);
      }
   }
   int[] mintree = new int[2*jj-1];
   for(int i = 2*jj-2; i >= 0; i--)
   {
      if(i>=jj-1)
      {
         if(i-(jj-1) < num+1)
         {
            mintree[i] = sums[i-(jj-1)];
         }
         else
         {
            mintree[i] = 2147483647;
         }
      }
      else
      {
         mintree[i] = Math.min(mintree[2*i+2], mintree[2*i+1]);
      }
   }
   
   
   int[] answers = new int[num];
   for(int i = 0; i < num; i++)
   {
      answers[i] = getMax(i+1, rights[i] + 1, 0, jj, 0, maxtree) - getMin(lefts[i], i+1, 0, jj, 0, mintree) - arr[i];
   }
   int max = answers[0];
   for(int i = 0; i < num; i++)
   {
      if(answers[i] > max)
      {
         max = answers[i];
      }
   }
   System.out.println("" + max);
}
public static int getMax(int l, int r, int a, int b, int i, int[] tree)
{
   if(a >= l && b <= r)
   {
      return tree[i];
   }
   if(a >= r || b <= l)
   {
      return -2147483647;
   }
   return Math.max(getMax(l, r, a, (a+b)/2, 2*i+1, tree), getMax(l, r, (a+b)/2, b, 2*i+2, tree));
}

public static int getMin(int l, int r, int a, int b, int i, int[] tree)
{
   if(a >= l && b <= r)
   {
      return tree[i];
   }
   if(a >= r || b <= l)
   {
      return 2147483647;
   }
   return Math.min(getMin(l, r, a, (a+b)/2, 2*i+1, tree), getMin(l, r, (a+b)/2, b, 2*i+2, tree));
}
static class Pair implements Comparable<Pair> {
final int a;
final int b;
Pair(int a, int b) {
this.a = a;
this.b = b;
}
@Override
public int compareTo(Pair other) {
if (a != other.a) {
return (a - other.a);
} else {
return -1*(b - other.b);
}}}
}
