CF1556C.Compressed Bracket Sequence

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, \dots, 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 \le 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.

威廉有一个最喜爱的括号序列。由于该序列长度较大，他以一个正整数序列 $c_1, c_2, \dots, c_n$ 的形式提供给你：当 $i$ 为奇数时，$c_i$ 表示连续左括号 "(" 的个数；当 $i$ 为偶数时，$c_i$ 表示连续右括号 ")" 的个数。

例如，对于括号序列 "((())()))"，其对应的数字序列为 $[3, 2, 1, 3]$。

你需要计算原始括号序列中，有多少个连续子序列（即子区间）$[l, r]$（满足 $l \le r$）是合法括号序列（regular bracket sequence）。

若能通过向该括号序列中插入字符 "+" 和 "1" 得到一个合法的算术表达式，则称该括号序列为合法括号序列。例如，"(())()"、"()" 和 "(())(()))" 是合法的，而 ")("、"(()" 和 "(())(" 则不是。

The first line contains a single integer $n$ $(1 \le n \le 1000)$, the size of the compressed sequence.

The second line contains a sequence of integers $c_1, c_2, \dots, c_n$ $(1 \le c_i \le 10^9)$, the compressed sequence.

第一行包含一个整数 $n$ $(1 \le n \le 1000)$，表示压缩序列的长度。

第二行包含一个整数序列 $c_1, c_2, \dots, c_n$ $(1 \le c_i \le 10^9)$，即压缩序列。

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.

输出一个整数——原括号序列中，合法括号序列的子段总数。

可以证明，答案在有符号 64 位整数数据类型范围内。

In the first example a sequence (((()(()))( is described. This bracket sequence contains $5$ subsegments which form regular bracket sequences:

1. Subsequence from the $3$rd to $10$th character: (()(()))
2. Subsequence from the $4$th to $5$th character: ()
3. Subsequence from the $4$th to $9$th character: ()(())
4. Subsequence from the $6$th to $9$th character: (())
5. Subsequence from the $7$th to $8$th character: ()

In the second example a sequence ()))(()(()))) is described.

In the third example a sequence ()()(()) is described.

在第一个例子中，描述了一个括号序列 (((()(()))( 。该括号序列包含 $5$ 个构成规则括号序列的子段：

1. 第 $3$ 个到第 $10$ 个字符构成的子序列：(()(()))
2. 第 $4$ 个到第 $5$ 个字符构成的子序列：()
3. 第 $4$ 个到第 $9$ 个字符构成的子序列：()((
4. 第 $6$ 个到第 $9$ 个字符构成的子序列：(())
5. 第 $7$ 个到第 $8$ 个字符构成的子序列：()

在第二个例子中，描述了一个括号序列 ()))(()(())))。

在第三个例子中，描述了一个括号序列 ()()(())。