该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

嘀，选手卡~

题目描述

蒙德城的某占星学家，阿斯托洛吉斯·莫娜·梅姬斯图斯，某天送给你了一条长度为 $n$ 的水晶项链。这个项链由 $n$ 颗水晶首尾连接成环构成，每颗水晶上都刻写了一个数字 $a_i$，被称之为这颗水晶的铭刻数。

同时，莫娜为了不让可莉再去四处炸鱼，给可莉出了这样一道题：

当项链某一段连续的水晶中，铭刻数为奇数的水晶的数量，与铭刻数为偶数的水晶的数量相等时，这一段水晶才是稳定的。

现在，莫娜希望可莉计算：要从项链中取出一段连续的稳定水晶，总共有多少种可行的方案？

这么难的问题，小可莉当然一点也不会啦！于是她来求助你，希望你能帮她做出这道题来，这样她就能继续去炸鱼啦~

注意，当两段水晶的起始位置不同，或结束位置不同，这两个方案就被视为不同方案，具体可参考样例。

输入格式

第 $1$ 行共一个正整数 $n$，表示项链包含的水晶数量。

第 $2$ 行包共 $n$ 个用空格隔开的整数 $a_1, a_2, a_3 \ldots a_n$，依次表示项链中每个水晶的铭刻数。由于项链首尾连接成环，因此$a_n$ 的下一个水晶为$a_1$。

输出格式

一个整数，表示从项链中取出一段稳定的水晶，总共包含的可行方案数。

样例 #1

样例输入 #1

6
1 3 2 4 3 2

样例输出 #1

14

样例 #2

样例输入 #2

见题目附加样例文件中的 ex.in。

样例输出 #2

见题目附加样例文件中的 ex.out。

（提升：文件选项在右边栏哦）

提示与说明

对于 $20\%$ 的数据，保证 $1 \le n \le 50$ 。

对于 $35\%$ 的数据，保证 $1 \le n \le 100$。

对于 $60\%$ 的数据，保证 $1 \le n \le 1000$。

对于 $100\%$ 的数据，保证 $1 \le n \le 10^6$，$1 \le a_1,a_2,a_3 \ldots a_n \le 10$。