description: <image>
  
  William has a favorite bracket sequence. Since his favorite sequence is quite big he provided it to you as a sequence of positive integers c_1, c_2, ..., c_n where c_i is the number of consecutive brackets "(" if i is an odd number or the number of consecutive brackets ")" if i is an even number.
  
  For example for a bracket sequence "((())()))" a corresponding sequence of numbers is [3, 2, 1, 3].
  
  You need to find the total number of continuous subsequences (subsegments) [l, r] (l ≤ r) of the original bracket sequence, which are regular bracket sequences.
  
  A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, sequences "(())()", "()" and "(()(()))" are regular, while ")(", "(()" and "(()))(" are not.
  
  Input
  
  The first line contains a single integer n (1 ≤ n ≤ 1000), the size of the compressed sequence.
  
  The second line contains a sequence of integers c_1, c_2, ..., c_n (1 ≤ c_i ≤ 10^9), the compressed sequence.
  
  Output
  
  Output a single integer — the total number of subsegments of the original bracket sequence, which are regular bracket sequences.
  
  It can be proved that the answer fits in the signed 64-bit integer data type.
  
  Examples
  
  Input
  
  
  5
  4 1 2 3 1
  
  
  Output
  
  
  5
  
  
  Input
  
  
  6
  1 3 2 1 2 4
  
  
  Output
  
  
  6
  
  
  Input
  
  
  6
  1 1 1 1 2 2
  
  
  Output
  
  
  7
  
  Note
  
  In the first example a sequence (((()(()))( is described. This bracket sequence contains 5 subsegments which form regular bracket sequences:
  
    1. Subsequence from the 3rd to 10th character: (()(()))
    2. Subsequence from the 4th to 5th character: ()
    3. Subsequence from the 4th to 9th character: ()(())
    4. Subsequence from the 6th to 9th character: (())
    5. Subsequence from the 7th to 8th character: ()
  
  
  
  In the second example a sequence ()))(()(()))) is described.
  
  In the third example a sequence ()()(()) is described.
solution: import static java.lang.Math.max;
  import static java.lang.Math.min;
  import static java.lang.Math.abs;
  import java.util.*;
  import java.io.*;
  
  public class A
  {
      static int n;
      static int[] arr;
      static char[] s;
      public static void main(String[] args) throws IOException
      {
          f = new Flash();
          out = new PrintWriter(System.out);
          
          int T = 1;//ni();
          for(int tc = 1; tc <= T; tc++){
          	n = ni(); arr = arr(n); sop(fn());
          }
          
          out.flush(); out.close();
      }
      
      //https://www.youtube.com/watch?v=7AHvvTWSsqY
      static long fn()
      {
          long[] open = new long[n];
          long[] close = new long[n];
          for(int i = 0; i < n; i++) {
          	if(i%2 == 0) open[i] += arr[i];
          	else close[i] += arr[i];
          }
          
          for(int i = 1; i < n; i++) {
          	open[i] += open[i-1];
          	close[i] += close[i-1];
          }
          
          long[][] ap = new long[n][n];
          for(int j = 0; j < n; j++) {
          	for(int i = j; i >= 0; i--) {
          		if(i==j) {
          			ap[i][j] = arr[i];
          			if(i%2 == 1) ap[i][j] *= -1;
          			continue;
          		}
          		
          		long cur = arr[i];
          		if(i%2 == 1) cur *= -1;
          		ap[i][j] = min(cur, cur + ap[i+1][j]);
          	}
          }
          
          long[][] dp = new long[n][n];
          for(int j = 0; j < n; j++) {
          	for(int i = j-1; i >= 0; i--) {
          		if(j == i+1) {
          			if(i%2 == 0) dp[i][j] = min(arr[i], arr[j]);
          			continue;
          		}
          		
          		dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
          		
          		if(i%2 == 1 || j%2 == 0) continue;
          		
          		long mv = ap[i+1][j-1];
          		mv = abs(mv);
          		
          		long totalOpen = open[j-1] - open[i];
          		long totalClose = close[j-1] - close[i];
          		
          		if(arr[i] < mv) continue;
          		totalOpen += mv;
          		if(arr[j] < (totalOpen-totalClose)) continue;
          		dp[i][j] += 1;
          		
          		long extraLeft = arr[i]-mv;
          		long extraRight = arr[j] - (totalOpen-totalClose);
          		dp[i][j] += min(extraLeft, extraRight);
          	}
          }
          
          return dp[0][n-1];
      }
      
      static Flash f;
      static PrintWriter out;
      static final long mod = (long)1e9+7;
      static final long inf = (long)1e18;
      static final int _inf = (int)1e9;
      static final int maxN = (int)1e6;
      static long[] fact, inv;
      
      static class cpr implements Comparator<int[]>{
      	public int compare(int[] a, int[] b) {
      		return Integer.compare(a[0], b[0]);
      	}
      }
      
      static void sort(int[] a){
          List<Integer> A = new ArrayList<>();
          for(int i : a) A.add(i);
          Collections.sort(A);
          for(int i = 0; i < A.size(); i++) a[i] = A.get(i);
      }
      
      static void sort(long[] a){
          List<Long> A = new ArrayList<>();
          for(long i : a) A.add(i);
          Collections.sort(A);
          for(int i = 0; i < A.size(); i++) a[i] = A.get(i);
      }
      
      static void print(int[] a){
          StringBuilder sb = new StringBuilder();
          for(int v : a) sb.append(v + " ");
          out.println(sb);
      }
      
      static void print(long[] a){
          StringBuilder sb = new StringBuilder();
          for(long v : a) sb.append(v + " ");
          out.println(sb);
      }
      
      static void print(List<Integer> A){
          StringBuilder sb = new StringBuilder();
          for(int v : A) sb.append(v + " ");
          out.println(sb);
      }
      
      static int swap(int itself, int dummy){return itself;}
      static long swap(long itself, long dummy){return itself;}
      static char swap(char itself, char dummy){return itself;}
      static void sop(Object o){out.println(o);}
      static int ni(){return f.ni();}
      static long nl(){return f.nl();}
      static double nd(){return f.nd();}
      static String next(){return f.next();}
      static String ns(){return f.ns();}
      static String yes = "YES", no = "NO";
      static char[] nc(){return f.nc();}
      static int[] arr(int len){return f.arr(len);}
      static int gcd(int a, int b){if(b == 0) return a; return gcd(b, a%b);}
      static long gcd(long a, long b){if(b == 0) return a; return gcd(b, a%b);}
      static int fcm(int a, int b){return (a*b)/gcd(a, b);}
      static long fcm(long a, long b){return (a*b)/gcd(a, b);}
      static double log2(long N) {return Math.log(N) / Math.log(2);}
      static void debug(int[] a) {sop(Arrays.toString(a));}
      static void debug(long[] a) {sop(Arrays.toString(a));}
      
      static class Flash
      {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer("");
          
          String next(){
              while(!st.hasMoreTokens()){
                  try{
                      st = new StringTokenizer(br.readLine());
                  }catch(IOException e){
                      e.printStackTrace();
                  }
              }
              
              return st.nextToken();
          }
          
          String ns(){
              String s = new String();
              try{
                  s = br.readLine().trim();
              }catch(IOException e){
                  e.printStackTrace();
              }
              
              return s;
          }
          
          int[] arr(int n){
              int[] a = new int[n];
              for(int i = 0; i < n; i++) a[i] = ni();
              return a;
          }
          
          char[] nc(){return ns().toCharArray();}
          int ni(){return Integer.parseInt(next());}
          long nl(){return Long.parseLong(next());}
          double nd(){return Double.parseDouble(next());}
      }
  }