思路

关键观察：将区间右端点从 $i-1$ 扩展到 $i$ 时，任何以 $i$ 结尾的子区间的按位或，要么等于 $a_i$，要么是某个以前缀结尾的按位或再与 $a_i$ 做一次 $|$。并且按位或只会“开新位”不会关掉已有位，因此对于固定右端点 $i$，不同的“以 $i$ 结尾的子区间按位或结果”的种类数是有限的，至多与二进制位数相关。由于 $a_i\le 10^9$，二进制位数 $B\le 31$，所以每个位置最多保留 $O(B)$ 个不同的结果。

做法（在线去重）：

• 维护两个集合：

  • $S_{\text{prev}}$：所有“以前一个位置结尾”的按位或结果集合；

题目内容

小红有一个长度为 $n$ 的数组 $a$ ，记子区间 $[l,r]$ 的权值为 $a_l|a_{l+1}|...|a_r$ ，即区间内所有数的按位或运算的结果。一共有 $n×(n+1)/2$ 个子区间，小红想知道对应的 $n×(n+1)/2$ 个权值中，有多少个不同的取值。

输入描述

第一行一个整数 $n$ ，表示数组长度。

第二行 $n$ 个整数 $a_1,a_2,...,a_n$ ，表示数组 $a$ 的元素。

$1 ≤n≤ 10^5$

$1 ≤ a_i ≤ 10^9$

输出描述

输出一个整数，表示不同的取值个数。

样例1

输入

3
1 2 4

输出

6

说明

$[1,1]$ 的权值为 $1$

$[1,2]$ 的权值为 $3$

$[1,3]$ 的权值为 $7$

$[2,2]$ 的权值为 $2$

$[2,3]$ 的权值为 $6$

$[3,3]$ 的权值为 $4$