У Василия есть его любимая скобочная последовательность. Так как последовательность имеет внушительный размер, Василий предоставил вам ее в виде последовательности положительных чисел \(c_1, c_2, \dots, c_n\), где \(c_i\) обозначает количество подряд идущих скобок «(» в случае, если \(i\) — нечетное число, либо количество подряд идущих скобок «)» в случае, если \(i\) — четное число.
К примеру, скобочной последовательности «((())()))» соответствует последовательность \([3, 2, 1, 3]\).
Вам необходимо найти количество подотрезков \([l, r]\) (\(l \le r\)) оригинальной скобочной последовательности, которые являются правильными скобочными последовательностями.
Напомним, что правильной скобочной последовательностью называется скобочная последовательность, которую можно преобразовать в корректное арифметическое выражение путем вставок между ее символами символов «1» и «+». Например, скобочные последовательности «(())()», «()» и «(()(()))» — правильные, а «)(», «(()» и «(()))(» — нет.
Выходные данные
Выведите одно целое число — количество отрезков оригинальной скобочной последовательности, которые являются правильными скобочными последовательностями.
Можно показать, что ответ помещается в знаковый 64-битный целочисленный тип данных.
Примечание
В первом тестовом примере описана скобочная последовательность (((()(()))(. В этой скобочной последовательности есть \(5\) отрезков, которые являются правильными скобочными последовательностями:
- Отрезок с \(3\) по \(10\) символ: (()(()))
- Отрезок с \(4\) по \(5\) символ: ()
- Отрезок с \(4\) по \(9\) символ: ()(())
- Отрезок с \(6\) по \(9\) символ: (())
- Отрезок с \(7\) по \(8\) символ: ()
Во втором тестовом примере описана скобочная последовательность ()))(()(()))).
В третьем тестовом примере описана скобочная последовательность ()()(()).