题目描述

给出了一个长度为$n$的数组$a_1,a_2,...,a_n$, 询问有多少区间满足区间内的偶数个数等于奇数个数。

输入格式

第一行包含一个正整数$n$

第二行包含$n$个数代表$a_i$

$1\le n\le 10^6, 1\le a_i \le10^9$

对于20%的数据，所有数都为偶数

对于另外20%的数据，$n\le 100$

对于另外30%的数据，$n\le 3000$

输出格式

输出一行一个数代表答案

样例输入

6
0 0 0 1 1 1

样例输出

3