C. Сжатая скобочная последовательность
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Василия есть его любимая скобочная последовательность. Так как последовательность имеет внушительный размер, Василий предоставил вам ее в виде последовательности положительных чисел $$$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$$$ отрезков, которые являются правильными скобочными последовательностями:

  1. Отрезок с $$$3$$$ по $$$10$$$ символ: (()(()))
  2. Отрезок с $$$4$$$ по $$$5$$$ символ: ()
  3. Отрезок с $$$4$$$ по $$$9$$$ символ: ()(())
  4. Отрезок с $$$6$$$ по $$$9$$$ символ: (())
  5. Отрезок с $$$7$$$ по $$$8$$$ символ: ()

Во втором тестовом примере описана скобочная последовательность ()))(()(()))).

В третьем тестовом примере описана скобочная последовательность ()()(()).