### 问题描述 小蓝对数组的奇偶最简比例很感兴趣，$f(x)$ 表示数组 $x$ 的奇偶最简比例，例如： - $f([1,2,3,4])=1:1$，表示数组 $[1,2,3,4]$ 的奇数个数和偶数个数最简比为 $1:1$； - $f([2,4,6])=0:1$； - $f([1,3,5])=1:0$。 现在给定一个长度为 $n$ 的数组 $a$，小蓝想知道存在多少个二元组 $$ 满足以下性质： 1. $1 \leq i < j \leq n$； 2. $f([a[1]...a[i]]) = f([a[j]...a[n]])$，即 $[a[1]...a[i]]$ 的奇偶最简比例等于 $[a[j]...a[n]]$ 的奇偶最简比例。 ### 输入格式 第一行为正整数 $n$，第二行为 $n$ 个正整数表示数组 ，其含义如上所述。 ### 输出格式 输出仅一行，包含一个整数，表示答案。 ### 样例输入 ```text 6 1 2 3 4 5 6 ``` ### 样例输出 ```text 3 ``` ### 说明 样例总共存在下面三种情况： 1. 二元组$<2,3>$：$f([1,2])=f([3,4,5,6])=1:1$； 2. 二元组$<2,5>$：$f([1,2])=f([5,6])=1:1$； 3. 二元组$<4,5>$：$f([1,2,3,4])=f([5,6])=1:1$。 ### 评测数据规模 对于 $50$% 的评测数据，$1\leq n \leq 10^3, 1 \leq a[i] \leq 10^9$； 对于 $100$% 的评测数据，$1\leq n \leq 10^5, 1 \leq a[i] \leq 10^9$。