← 返回题目列表

Codeforces · 1556/C

C. 压缩括号序列

中文机器翻译题面 查看原题

William 有一个最喜欢的括号序列。由于他最喜欢的序列相当大,因此他将其作为正整数序列 $$$c_1, c_2, \dots, c_n$$$ 提供给您,其中 $$$c_i$$$ 是连续括号的数量“(”如果 $$$i$$$ 是奇数或连续括号的数量“)”如果 $$$i$$$ 是偶数。

例如,对于括号序列“((())()))”,相应的数字序列是 $$$[3, 2, 1, 3]$$$。

需要求出原括号序列的连续子序列(子段)$$$[l, r]$$$ ($$$l \le r$$$) 的总数,这些子序列是正则括号序列。

如果通过在序列中插入字符“+”和“1”可以获得正确的算术表达式,则该序列称为正则括号序列。例如,序列“(())()”、“()”和“(()(()))”是规则的,而“)(”、“(()”和“(()))(”则不是。

输入

第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 1000)$$$,压缩序列的大小。

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

输出

输出一个整数——原始括号序列的子段总数,这些子段是常规括号序列。

可以证明答案符合带符号的64位整数数据类型。

示例

输入 #1

5
4 1 2 3 1

输出 #1

5

输入 #2

6
1 3 2 1 2 4

输出 #2

6

输入 #3

6
1 1 1 1 2 2

输出 #3

7

注意

在第一个示例中,描述了一个序列 (((()(()))(。该括号序列包含 $$$5$$$ 子段,它们形成常规括号序列:

1. 从 $$$3$$$rd 到第 $$$10$$$ 个字符的子序列:(()(()))
2. 从第 $$$4$$$ 到第 $$$5$$$ 字符的子序列:()
3. 从第 $$$4$$$ 到第 $$$9$$$ 字符的子序列: ()(())
4. 从第 $$$6$$$ 到第 $$$9$$$ 字符的子序列:(())
5. 从第 $$$7$$$ 到第 $$$8$$$ 字符的子序列:()

在第二个示例中,描述了序列 ()))(()(())))。

在第三个示例中描述了序列()()(())。