和为偶数的连续区间

题目描述

给定长度为 n 的非负整数序列，求元素和为偶数的非空连续区间数量。连续区间由一对下标 l、r 确定，满足 1≤l≤r≤n。

输入格式

第一行输入整数 n，满足 1≤n≤2×10^5。第二行输入 n 个整数 a1,a2,…,an，满足 0≤ai≤10^18。

输出格式

输出元素和为偶数的非空连续区间数量。答案可能超过 32 位整数范围。

样例

输入

4
1 2 3 4

输出

4