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$$$ 字符的子序列:()
在第二个示例中,描述了序列 ()))(()(())))。
在第三个示例中描述了序列()()(())。