Аналитик изучает временной ряд из n значений. Для каждого непрерывного периода он хочет понять, в скольких случаях количество чётных значений совпадает с количеством нечётных.

Требуется посчитать число таких периодов.

Иными словами, нужно найти количество непрерывных отрезков массива, на которых чётных элементов ровно столько же, сколько нечётных.

Входные данные

Первая строка содержит целое число n — количество значений.

Вторая строка содержит n целых чисел a_i — элементы массива.

Выходные данные

Выведите одно число — количество непрерывных периодов, в которых число чётных значений равно числу нечётных.

Ответ может не помещаться в 32-битный целочисленный тип.

Ограничения

1 <= n <= 2 * 10^5

-10^9 <= a_i <= 10^9

Примеры

Пример 1

Входные данные

5
1 2 3 4 5

Выходные данные

6

Пояснение

Здесь 6 подотрезков содержат поровну чётных и нечётных элементов.

Пример 2

Входные данные

1
2

Выходные данные

0