Compressed Bracket Sequence

题意翻译

给一个长度为 $n\,(1\le n\le 1000)$ 的正整数序列 $\left\{c_n\right\}\,(1\le c_i\le 10^9)$。用该序列一如下方式构造一个括号序列 $s$： 1. 开始 $c$ 为空； 2. 对 $i$ 从 $1$ 到 $n$ 依次遍历，若 $i$ 为奇数，则在 $s$ 后插入 $c_i$ 个 `'('`，否则插入 $c_i$ 个 `')'`。 求有多少对 $\left<l,r\right>$ 使得 $s_{l\sim r}$ 为合法括号序列。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #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

说明

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.