有趣的区间

有趣的区间

题号：NC231997
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给出一个长度为 $n$ 的数组 $A$ ，下标从 $1$ 开始， $A_1,A_2,...,A_n$ 。定义一个区间 $[l,r]$ 是“有趣的区间”，当且仅当 $A_l \mid A_{l+1} \mid A_{l+2} \mid ... \mid A_{r-1} \mid A_{r}$ 结果为奇数。

$a \mid b$ 表示 $a$ 按位或 $b$ （按位或运算符“ $\mid$ ”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的两个二进位有一个为 $1$ 时，结果位就为 $1$ ）。

求“有趣的区间”的个数，两个区间 $[L1,R1],[L2,R2]$ 相同，当且仅当 $L1=L2$ 且 $R1=R2$ 。

输入描述:

第一行包含一个整数 $n$ $(1\le n\le 5e5)$ ，表示数组 $A$ 的长度。

第二行包含 $n$ 个整数，分别表示数组 $A$ 的 $n$ 个元素，其中 $0\le A_i\le 1e9$ 。

输出描述:

一行包含一个整数，表示 ”有趣的区间“ 的个数。

示例1

输入

复制

2
2 1

输出

复制

说明

”有趣的区间“ 有

$[1,2]$ $($ $2 \mid 1 = 3$ 是奇数 $)$

$[2,2]$ $($ $1$ 是奇数 $)$

共 $2$ 个。