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.
Using python3 can you solve the prior task?

Can you provide a Python code 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 code to find the total number of continuous subsequences (subsegments) [l, r] (l ≤ r) of the original bracket sequence, which are regular bracket sequences.

import sys

#comment these out later
#sys.stdin = open("in.in", "r")
#sys.stdout = open("out.out", "w")

input = sys.stdin.readline

def main():
	#t = int(input())
	t = 1

	class RangeQuery:
	    def __init__(self, data, func=min):
	        self.func = func
	        self._data = _data = [list(data)]
	        i, n = 1, len(_data[0])
	        while 2 * i <= n:
	            prev = _data[-1]
	            _data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
	            i <<= 1

	    def query(self, start, stop):
	        """func of data[start, stop)"""
	        depth = (stop - start).bit_length() - 1
	        return self.func(self._data[depth][start], self._data[depth][stop - (1 << depth)])

	    def __getitem__(self, idx):
	        return self._data[0][idx]

	for _ in range(t):
		n = int(input())
		ar = list(map(int, input().split()))

		
		signs = [0]

		#pre = [0]

		for i, x in enumerate(ar):
			if i%2:
				signs.append(signs[-1]-x)
			else:
				signs.append(signs[-1]+x)

			#pre.append(pre[-1] + signs[-1])

		rq = RangeQuery(signs, min)
		

		ans = 0

		for l in range(0, n, 2):
			for r in range(l+1, n, 2):

				left = ar[l]
				right = ar[r]

				if r-l == 1:
					ans += min(left, right)
					continue

				stuff = signs[r] - signs[l+1]

				#print(l, r, signs[l+2:r+1], signs[l+1])

				minleft = rq.query(l+2, r+1) - signs[l+1]

				minleft = max(-minleft, 1)

				equivmin = stuff + minleft

				#print(l, r, left, right, minleft, equivmin, stuff)

				ans += max(min(left-minleft+1, right-equivmin+1), 0)

				#print(ans)

		print(ans)





main()