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: // Problem: Compressed Bracket Sequence
  // https://codeforces.com/contest/1556/problem/C
  // This submission:
  
  import java.util.*;
  
  public class CompressedBracketSequence {
  
    private static class BracketPair {
      private final long open, close;
  
      private BracketPair(long openInput, long closeInput) {
        open = openInput;
        close = closeInput;
      }
    }
  
    // The (input) brackets grouped into pairs of consecutive open brackets followed by consecutive
    // close brackets.
    private static ArrayList<BracketPair> v;
  
    // Returns the number of subsegments that forms regular bracket sequences using brackets
    // from `v`.
    private static long solve() {
      long result = 0;
  
      // Keeps track of the amount of open brackets we can use at the beginning. 
      long open = 0;
  
      for (int i = 0; i < v.size(); ++i) {
        BracketPair p = v.get(i);
        open += p.open;
  
        if (open < p.close) {
          // The sequence of `p.close` close brackets blocks any additional valid solutions that
          // starts with the `open` brackets at the beginning.
          result += open;
          open = 0;
        } else {
          // open >= p.close >= 1
          // For `(p.close - 1)` of the open brackets, they cannot be extended further (blocked
          // by the `p.close` close brackets).
          // One of the open bracket (starts with exactly `p.close` open brackets at the beginning)
          // is ended by the `p.close` close brackets. This subsegment can stop (one configuration),
          // or be further extended (`f(i + 1)` configurations).
          result += (p.close - 1) + 1 + f(i + 1);
          open -= p.close;
        }
      }
      return result;
    }
  
    // Cache for function `f`.
    // Memoization is beneficial because both `solve` and `f` calls `f`.
    private static Long[] f;
  
    // Returns the number of subsegments that starts at the beginning of `v[i, ]`
    // (i.e., prefixes of brackets of `v[i, ]`) that forms regular bracket sequences.
    private static long f(int i) {
      if (i >= v.size()) {
        return 0;
      }
  
      if (f[i] != null) {
        return f[i];
      }
  
      long open = 0;
      long close = 0;
      for (int k = i; k < v.size(); ++k) {
        open += v.get(k).open;
        close += v.get(k).close;
  
        if (open < close) {
          // Further extension is blocked by the `p.close` close brackets.
          return f[i] = 1L;
        } else if (open == close) {
          // We can stop with `close` close brackets (one configuration), or further extend
          // (`f(k + 1)` configurations).
          return f[i] = 1 + f(k + 1);
        }
  
        // There aren't enough close brackets yet. Go to the next bracket pair until we found
        // enough close brackets.
      }
    
      return f[i] = 0L;
    }
  
    public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
  
      int n = in.nextInt();
      v = new ArrayList<>();
  
      // Note: We do not need to read the last segment of open brackets when `n` is odd.
      // Those open brackets will not get matched in any regular bracket sequences.
      for (int i = 0; i + 1 < n; i += 2) {
        int open = in.nextInt();
        int close = in.nextInt();
        v.add(new BracketPair(open, close));
      }
  
      f = new Long[v.size()];
  
      System.out.println(solve());
      in.close();
    }
  }
  