题目描述

给定一个长度为 $n$ 的非负整数序列 $a$。

对于非空的非负整数集合 $S=\{s_1,s_2,\cdots,s_k\}$，如下定义两个函数：

• 定义 $\text{OR}(S)=s_1\lor s_2\lor\cdots\lor s_k$，即集合 $S$ 中所有元素进行按位或运算所得的结果。其中 $\lor$ 表示按位或运算。
• 定义 $\text{MEX}(S)=\min\{x\in\mathbb N \mid x\notin S\}$，即不在集合 $S$ 中的最小非负整数。

对于区间 $[l,r]$（$1\le l\le r\le n$），如下定义它的价值 $f(l,r)$：

• 设 $S=\{a_l,a_{l+1},\cdots,a_r\}$；
• $f(l,r)=\text{OR}(S)\lor\text{MEX}(S)$。其中 $\lor$ 表示按位或运算。

你的任务是求出 $\sum_{1\le l\le r\le n}f(l,r)$，即所有区间的价值和。答案对 $2^{64}$ 取模。

输入格式

本题输入量较大，请注意选择较快的输入方式。

输入的第一行包含一个正整数 $n$，表示序列的长度。

输入的第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行一个非负整数，表示所有区间的价值之和对 $2^{64}$ 取模后的结果。

3
0 1 2

13

4
1 0 1 3

24

10
536870912 0 1 2 3 536870912 1073741823 0 0 1

35970351152

提示

【样例 1 解释】

序列为 $[0,1,2]$，共有 $6$ 个区间。

以区间 $[1,2]$ 为例，其中的数构成集合 $S=\{0,1\}$，有 $\text{OR}(S)=1$，$\text{MEX}(S)=2$，因此 $f(1,2)=1\lor 2=3$。

各个区间的价值分别为：

• $f(1,1)=1$，$f(2,2)=1$，$f(3,3)=2$；
• $f(1,2)=3$，$f(2,3)=3$；
• $f(1,3)=3$。

因此，所有区间的价值之和为 $1+1+2+3+3+3=13$。

【样例 2 解释】

序列为 $[1,0,1,3]$，共有 $10$ 个区间。

以区间 $[1,3]$ 为例，其中的数为 $1,0,1$，构成的集合为 $S=\{0,1\}$。有 $\text{OR}(S)=1$，$\text{MEX}(S)=2$，因此 $f(1,3)=1\lor 2=3$。

长度为 $1$ 的四个区间的价值依次为 $1,1,1,3$，其余六个区间的价值均为 $3$。

因此，所有区间的价值之和为 $1+1+1+3+6\times 3=24$。

【样例 4】

见选手目录下的 func/func4.in 与 func/func4.ans。

该样例满足测试点 $3$ 的条件限制。

【样例 5】

见选手目录下的 func/func5.in 与 func/func5.ans。

该样例满足测试点 $8$ 的条件限制。

【样例 6】

见选手目录下的 func/func6.in 与 func/func6.ans。

该样例满足测试点 $12$ 的条件限制。

【样例 7】

见选手目录下的 func/func7.in 与 func/func7.ans。

该样例满足测试点 $17\sim 20$ 的条件限制。

【数据范围】

对于所有测试数据，保证：

• $1\leq n\leq 2\times 10^6$；
• 对于所有 $1\le i\le n$，均有 $0\leq a_i<2^{30}$。

测试点编号	$n\leq$	$a_i <$	特殊性质
$1$	$10$	$4$	×
$2$	$100$	$2^{10}$	^
$3$	$1\,000$	$2^{20}$
$4$	$3\,000$	^
$5\sim 6$	$5\,000$	$2^{30}$
$7$	$2\times 10^4$	^	$\checkmark$
$8$	$5\times 10^4$		^
$9\sim 10$	$10^5$		×
$11$	^	$2^{10}$	^
$12$	$2\times 10^5$	$2^{20}$
$13$	^	$2^{30}$
$14$	$5\times 10^5$	^
$15$	$10^6$	$2^{10}$	$\checkmark$
$16$	$1.5\times 10^6$	$2^{20}$	^
$17\sim 20$	$2\times 10^6$	$2^{30}$	×

特殊性质：对于所有 $1\le i\le n$，$a_i$ 在对应测试点规定的取值范围内独立、均匀随机生成。