CF1556C Compressed Bracket Sequence

 William 有一个最喜欢的括号序列。由于他最喜欢的序列非常大，他用一个正整数序列 $c_1, c_2, \dots, c_n$ 来表示，其中 $c_i$ 表示连续的括号数量：如果 $i$ 是奇数，则表示连续 $c_i$ 个左括号“(”，如果 $i$ 是偶数，则表示连续 $c_i$ 个右括号“)”。 例如，对于括号序列“((())()))”，对应的数字序列为 $[3, 2, 1, 3]$。 你需要求出原括号序列中有多少个连续子序列（子区间）$[l, r]$（$l \le r$），它们本身是合法的括号序列。 一个括号序列被称为合法（regular），当且仅当可以通过在括号之间插入字符“+”和“1”得到一个正确的算术表达式。例如，“(())()”、“()”和“(()(()))”是合法的，而“) (”、“(()”和“(())) (”是不合法的。

第一行包含一个整数 $n$（$1 \le n \le 1000$），表示压缩序列的长度。 第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le 10^9$），表示压缩后的括号序列。

输出一个整数，表示原括号序列中有多少个子区间是合法的括号序列。 可以保证答案不会超过有符号 64 位整数的范围。

在第一个样例中，括号序列为“(((()(()))(”，其中包含 $5$ 个合法的括号子区间： 1. 第 $3$ 到第 $10$ 个字符：(()(())) 2. 第 $4$ 到第 $5$ 个字符：() 3. 第 $4$ 到第 $9$ 个字符：()(()) 4. 第 $6$ 到第 $9$ 个字符：(()) 5. 第 $7$ 到第 $8$ 个字符：() 在第二个样例中，括号序列为“()))(()(())))”。 在第三个样例中，括号序列为“()()(())”。 由 ChatGPT 4.1 翻译