有$N$个男女同学随机排成一队，老师决定取其中一段，要求这段的男女人数要一样多。问有多数种取法？ 例如$N=6$，用1表示男生，用$0$表示女生，排队的情况是110001。可取方案有$4$段：1100、10001、10、01。

输入格式

第一行$1$个正整数：$N$。$N$范围$[1, 1000000]$。 第$N$个整数$F_i$。$F_i=1$表示男生，$F_i=0$表示女生。

输出格式

一个整数，可分成的最多方案数。

输入输出样例

输入 #1

6 0 0 0 1 1 1

输出 #1

3