Compressed Bracket Sequence
Contest: Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 1800
Tags: brute force, implementation

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.

Input format:
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 format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
5
4 1 2 3 1

Example output:
5

Example input:
6
1 3 2 1 2 4

Example output:
6

Editorial:
Let's examine a compressed sequence and fix two indexes $$$l < r, l$$$ % $$$2 = 0, r$$$ % $$$2 = 1$$$. Note that it makes no sense to examine other indexes because the correct bracket sequence always begins with the opening bracket and ends with the closing one.
Next, we can calculate the minimum bracket balance on the segment from $$$l + 1$$$ to $$$r - 1$$$. The minimum bracket balance is the minimum number of opening brackets that we must put before the sequence of brackets in order for it to be regular, provided that we can put any number of closing brackets at the end. Let's denote this number as $$$minBalance$$$, and denote the sum of $$$-c_{l + 1} + c_{l + 2} - c_{l + 2} + \dots$$$ as $$$balance$$$.
The next observation is that if we fix the number of opening brackets taken from $$$c_l$$$, then we can count the number of brackets that we should take from $$$c_r$$$. Using these observations we can calculate the answer for $$$l..r$$$ using the following formula: $$$min(c_l, c_r-balance) - max(1, minBalance) + 1$$$.
Note that this problem could also be solved in $$$O(n)$$$, but this was not required.