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: class SegTree:
      def __init__(self, init_val, ide_ele, segfunc):
          self.n = len(init_val)
          self.num = 2**(self.n-1).bit_length()
          self.ide_ele = ide_ele
          self.segfunc = segfunc
          self.seg = [ide_ele]*2*self.num
          # set_val
          for i in range(self.n):
              self.seg[i+self.num] = init_val[i]
          # built
          for i in range(self.num-1, 0, -1):
              self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])
  
      def update(self, k, x):
          k += self.num
          self.seg[k] = x
          while k:
              k = k >> 1
              self.seg[k] = self.segfunc(self.seg[2*k], self.seg[2*k+1])
  
      def query(self, l, r):
          if r <= l:
              return self.ide_ele
          l += self.num
          r += self.num
          lres = self.ide_ele
          rres = self.ide_ele
          while l < r:
              if r & 1:
                  r -= 1
                  rres = self.segfunc(self.seg[r], rres)
              if l & 1:
                  lres = self.segfunc(lres, self.seg[l])
                  l += 1
              l = l >> 1
              r = r >> 1
          res = self.segfunc(lres, rres)
          return res
  
      def __str__(self): # for debug
          arr = [self.query(i,i+1) for i in range(self.n)]
          return str(arr)
  
  def segfuncm(x, y):
      if x <= y:
          return x
      else:
          return y
  
  def segfuncM(x, y):
      if x >= y:
          return x
      else:
          return y
  
  INF = 1 << 60
  
  def main():
      n = int(input())
      C = list(map(int, input().split()))
  
      CS = [0]*(n+1)
      for i in range(n):
          if i%2 == 0:
              CS[i+1] = CS[i]+C[i]
          else:
              CS[i+1] = CS[i]-C[i]
      #print(CS)
      segm = SegTree(CS, INF, segfuncm)
      segM = SegTree(CS, -INF, segfuncM)
  
      ans = 0
      for l in range(n):
          if l%2 == 1:
              continue
          for r in range(l, n):
              if r%2 == 0:
                  continue
              x = CS[r]-CS[l+1]
              #print(l, r, x)
              a = C[l]
              b = C[r]
              m = segm.query(l+2, r+1)-CS[l+1]
              #print(segm.query(l+1, r+1), CS[l+1])
              M = segM.query(l+2, r+1)-CS[l+1]
              #print(segM.query(l+1, r+1), CS[l+1])
              p = max(1, 1-x, -m)
              q = min(a, b-x)
              #print(l, r, p, q, m, M)
              if q < p:
                  continue
              else:
                  ans += q-p+1
  
  
      print(ans)
  
  if __name__ == '__main__':
      main()
  