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 java.io.*;
  import java.util.*;
   public class Main {
  	public static void main(String[] args) throws Exception {
  		FastIO io = new FastIO();
  		int test=1;
  		while(test>0)
  		{
  		    int n=io.nextInt();
  		    long arr[]=new long[n];
  		    for(int i=0;i<n;i++)arr[i]=io.nextLong();
  		    long count[]=new long[n];
  		    int sp[]=new int[n];
  		    long ans=0;
  		    for(int i=0;i<n;i++)
  		    {
  		        if(i%2==0)
  		        {
  		            if(i==0)continue;
  		            int j=i-1;
  		            while(j>=0)
  		            {
  		                if(arr[j]!=0)break;
  		                if(j%2==1)
  		                {
  		                    count[i]++;
  		                    j=sp[j];
  		                }
  		                else
  		                {
  		                    j--;
  		                }
  		            }
  		            //io.println(i+" "+count[i]);
  		        }
  		        else
  		        {
  		            int j=i-1;
  		            while(j>=0)
  		            {
  		                if(j%2==1)
  		                {
  		                    if(arr[j]>0){
  		                        sp[i]=j+1;
  		                        break;
  		                    }
  		                    j--;
  		                    continue;
  		                }
  		                if(arr[j]>=arr[i])
  		                {
  		                    if(arr[i]==arr[j])ans+=count[j];
  		                    arr[j]-=arr[i];
  		                    ans+=arr[i];
  		                    arr[i]=0;
  		                    sp[i]=j;
  		                    break;
  		                }
  		                arr[i]-=arr[j];
  		                if(arr[j]!=0)
  		                {
  		                    ans+=arr[j]+count[j];
  		                    arr[j]=0;
  		                }
  		                j-=1;
  		            }
  		            if(j<0)sp[i]=-1;
  		        }
  		    }
  		    io.println(ans);
  		    test--;
  		}
  		io.close();
  	}
  }
   
   class FastIO extends PrintWriter {
  	private InputStream stream;
  	private byte[] buf = new byte[1<<16];
  	private int curChar, numChars;
   
  	// standard input
  	public FastIO() { this(System.in,System.out); }
  	public FastIO(InputStream i, OutputStream o) {
  		super(o);
  		stream = i;
  	}
  	// file input
  	public FastIO(String i, String o) throws IOException {
  		super(new FileWriter(o));
  		stream = new FileInputStream(i);
  	}
   
  	// throws InputMismatchException() if previously detected end of file
  	private int nextByte() {
  		if (numChars == -1) throw new InputMismatchException();
  		if (curChar >= numChars) {
  			curChar = 0;
  			try {
  				numChars = stream.read(buf);
  			} catch (IOException e) {
  				throw new InputMismatchException();
  			}
  			if (numChars == -1) return -1; // end of file
  		}
  		return buf[curChar++];
  	}
   
  	public String nextLine() {
  		int c; do { c = nextByte(); } while (c <= '\n');
  		StringBuilder res = new StringBuilder();
  		do { res.appendCodePoint(c); c = nextByte(); } while (c > '\n');
  		return res.toString();
  	}
   
  	public String next() {
  		int c; do { c = nextByte(); } while (c <= ' ');
  		StringBuilder res = new StringBuilder();
  		do { res.appendCodePoint(c); c = nextByte(); } while (c > ' ');
  		return res.toString();
  	}
   
  	public int nextInt() { 
  		int c; do { c = nextByte(); } while (c <= ' ');
  		int sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
  		int res = 0;
  		do {
  			if (c < '0' || c > '9')
  				throw new InputMismatchException();
  			res = 10*res+c-'0';
  			c = nextByte();
  		} while (c > ' ');
  		return res * sgn;
  	}
   
    public long nextLong() { 
  		int c; do { c = nextByte(); } while (c <= ' ');
  		long sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
  		long res = 0;
  		do {
  			if (c < '0' || c > '9')
  				throw new InputMismatchException();
  			res = 10*res+c-'0';
  			c = nextByte();
  		} while (c > ' ');
  		return res * sgn;
  	}
   
  	public double nextDouble() { return Double.parseDouble(next()); }
  }