У Василия есть его любимая скобочная последовательность. Так как последовательность имеет внушительный размер, Василий предоставил вам ее в виде последовательности положительных чисел $$$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-битный целочисленный тип данных.
5 4 1 2 3 1
5
6 1 3 2 1 2 4
6
6 1 1 1 1 2 2
7
В первом тестовом примере описана скобочная последовательность (((()(()))(. В этой скобочной последовательности есть $$$5$$$ отрезков, которые являются правильными скобочными последовательностями:
- Отрезок с $$$3$$$ по $$$10$$$ символ: (()(()))
- Отрезок с $$$4$$$ по $$$5$$$ символ: ()
- Отрезок с $$$4$$$ по $$$9$$$ символ: ()(())
- Отрезок с $$$6$$$ по $$$9$$$ символ: (())
- Отрезок с $$$7$$$ по $$$8$$$ символ: ()
Во втором тестовом примере описана скобочная последовательность ()))(()(()))).
В третьем тестовом примере описана скобочная последовательность ()()(()).
