You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

世界上最棒的运动大概是棒球，因为其他的运动都没有棒球棒。

请注意本题极为特殊的时空限制，保证时间限制在 std 1.5 倍以上，空间限制在 std 3 倍以上。

题目描述

给定一个长度为 $n$ 的序列，求出有多少个区间 $[l, r]$，满足 $\forall l \leq i < j \leq r$，$a_i \& a_j = 0$。

特别的，$l=r$ 时也视为满足该条件。

输入格式

第一行，一个正整数 $n$。

接下来一行 $n$ 个非负整数，第 $i$ 个数表示 $a_i$。

输出格式

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

输入输出样例 #1

输入 #1

5
1 4 3 2 4

输出 #1

8

说明/提示

数据范围

本题采用捆绑测试计分。

对于所有数据，保证 $1 \le n \le 5 \times 10^6,0 \le a_i \le 2^{32}-1$。