Боб решил отдохнуть от домашних заданий по матанализу и придумал для себя игру.
Игра происходит на последовательности куч камней, которая может быть представлена как массив \(s_1, \ldots, s_k\), где \(s_i\) — количество камней в \(i\)-й куче. За один ход Боб выбирает две соседние непустые кучи \(i\) и \(i+1\) и убирает по одному камню из каждой. Если куча стала пустой, то её соседи не становятся соседними. Игра заканчивается, когда у Боба нет доступных ходов. Боб считает, что он выиграл, если в конце игры все кучи стали пустыми.
Мы считаем последовательность куч выигрышной, если Боб может начать с неё и выиграть после некоторой последовательности ходов.
Вам дана последовательность \(a_1, \ldots, a_n\), посчитайте количество выигрышных подотрезков \(a\). Другими словами, найдите количество отрезков \([l, r]\) (\(1 \leq l \leq r \leq n\)) таких, что \(a_l, a_{l+1}, \ldots, a_r\) является выигрышной последовательностью куч.
Выходные данные
Для каждого набора входных данных выведите единственное целое число — ответ на задачу.
Примечание
В первом наборе входных данных Боб не может выиграть с подотрезками длины \(1\), так как нет ни одной пары соседних куч для массива длины \(1\).
Во втором наборе входных данных каждый подотрезок не является выигрышным.
В четвертом наборе входных данных подотрезок \([1, 4]\) выигрышный, потому что Боб может сделать ходы со следующими парами соседних кучек: \((2, 3)\), \((1, 2)\), \((3, 4)\). Другой выигрышный подотрезок это \([2, 3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2
2 2
3
1 2 3
4
1 1 1 1
4
1 2 2 1
4
1 2 1 2
8
1 2 1 2 1 2 1 2
|
1
0
4
2
1
3
|