human
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.

Can you provide a Python program to find the total number of continuous subsequences (subsegments) [l, r] (l ≤ r) of the original bracket sequence, which are regular bracket sequences?
assistant
#Here is Python program to find the total number of continuous subsequences (subsegments) [l, r] (l ≤ r) of the original bracket sequence, which are regular bracket sequences.

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 =...