题目描述

给你一个长度为 $n$ 的正整数序列 $a_1,a_2,...,a_n$。
现在定义函数：

$$f(i,j)=\left\{ \begin{aligned} 0 \quad (a_i+a_{i+1}+...+a_j)\space mod\space 2=1\\ 1 \quad (a_i+a_{i+1}+...+a_j)\space mod\space 2=0\\ \end{aligned} \right . $$

现在问你：

$$\sum_{i=1}^n\sum_{j=i}^nf(i,j)$$

的值为多少？

注意：$x\space mod\space y$ 代表 $x$ 对 $y$ 取余数的结果。

输入格式

第一行一个正整数 $n$。
第二行 $n$ 个正整数 $a_1,a_2,...,a_n$。

输出格式

一行一个整数，表示答案。

输入输出样例 #1

输入 #1

5
3 2 1 4 5

输出 #1

6

输入输出样例 #2

输入 #2

10
111 222 333 444 555 666 777 888 999 666

输出 #2

25

说明/提示

数据范围：$1\le n\le 5\times 10^5,1\le a_i\le 10^9$。