题目背景 嘀，选手卡~

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

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

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

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

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

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

输入格式 第 1 1 行共一个正整数 ? n，表示项链包含的水晶数量。

第 2 2 行包共 ? n 个用空格隔开的整数 ? 1 , ? 2 , ? 3 … ? ? a 1 ​ ,a 2 ​ ,a 3 ​ …a n ​ ，依次表示项链中每个水晶的铭刻数。由于项链首尾连接成环，因此 ? ? a n ​ 的下一个水晶为 ? 1 a 1 ​ 。

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

样例 #1 样例输入 #1 6 1 3 2 4 3 2 样例输出 #1 14 提示与说明 对于 20 % 20% 的数据，保证 1 ≤ ? ≤ 50 1≤n≤50 。

对于 35 % 35% 的数据，保证 1 ≤ ? ≤ 100 1≤n≤100。

对于 60 % 60% 的数据，保证 1 ≤ ? ≤ 1000 1≤n≤1000。

对于 100 % 100% 的数据，保证 1 ≤ ? ≤ 1 0 6 1≤n≤10 6 ， 1 ≤ ? 1 , ? 2 , ? 3 … ? ? ≤ 10 1≤a 1 ​ ,a 2 ​ ,a 3 ​ …a n ​ ≤10。