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.util.Random;
  import java.util.Scanner;
  import java.util.Stack;
  
  public class Main {
      public static void main(String[] args) {
          Random random = new Random();
          Scanner scanner = new Scanner(System.in);
          int n = scanner.nextInt();
          int[] array = new int[n];
          for (int i = 0; i < n; i++) {
              array[i] = scanner.nextInt();
  //            array[i] = random.nextInt(100000)+1;
  //            System.out.println(array[i]);
          }
          if(n==1){
              System.out.println(0);
              return;
          }
          long cnt = 0;
          Stack<node> stack = new Stack<>();
          int[] provide = new int[n];
          int lc = array[0];
          int rc = array[1];
          if (lc == rc) {
              cnt += lc;
              provide[0] = 1;
          } else if (lc > rc) {
              cnt += rc;
              stack.push(new node(lc - rc, 0));
              provide[0] = 1;
          } else if (lc < rc) {
              cnt += lc;
              provide[0] = 0;
          }
          for (int i = 2; i < (array.length % 2 == 0 ? array.length : array.length - 1); i += 2) {
              int l = array[i];
              int r = array[i + 1];
              if (l == r) {
                  cnt += l;
                  cnt += provide[i - 2];
                  provide[i] = provide[i - 2] + 1;
              } else if (l > r) {
                  cnt += r;
                  stack.push(new node(l - r, i));
                  provide[i] = 1;
              } else if (l < r) {
                  cnt += l;
                  cnt+=provide[i-2];
                  int cur = r - l;
                  while (true) {
                      if(stack.empty()){
                          provide[i] = 0;
                          break;
                      }
                      node peek = stack.peek();
                      if (peek.count > cur){
                          cnt+=cur;
                          peek.count -= cur;
                          provide[i] = 1;
                          break;
                      }else if(peek.count==cur){
                          cnt+=cur;
                          cnt+=peek.index==0?0:provide[peek.index-2];
                          stack.pop();
                          provide[i] = peek.index==0?0:provide[peek.index-2]+1;
                          break;
                      }else{
                          cnt+=peek.count;
                          cnt+=peek.index==0?0:provide[peek.index-2];
                          stack.pop();
                          cur-=peek.count;
                      }
                  }
  
              }
          }
          System.out.println(cnt);
  
      }
  
      static class node {
          long count;
          int index;
  
          public node(long count, int index) {
              this.count = count;
              this.index = index;
          }
      }
  }