codeforces#P1556C. Compressed Bracket Sequence
Compressed Bracket Sequence
Description

William has a favorite bracket sequence. Since his favorite sequence is quite big he provided it to you as a sequence of positive integers where is the number of consecutive brackets "(" if is an odd number or the number of consecutive brackets ")" if is an even number.
For example for a bracket sequence "((())()))" a corresponding sequence of numbers is .
You need to find the total number of continuous subsequences (subsegments) () 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 , the size of the compressed sequence.
The second line contains a sequence of integers , 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.
Input
The first line contains a single integer , the size of the compressed sequence.
The second line contains a sequence of integers , the compressed sequence.
Output
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.
Samples
Note
In the first example a sequence (((()(()))( is described. This bracket sequence contains subsegments which form regular bracket sequences:
- Subsequence from the rd to th character: (()(()))
- Subsequence from the th to th character: ()
- Subsequence from the th to th character: ()(())
- Subsequence from the th to th character: (())
- Subsequence from the th to th character: ()
In the second example a sequence ()))(()(()))) is described.
In the third example a sequence ()()(()) is described.