A. The Brand New Function

题目大意

Polycarpus有一个由n个非负整数组成的序列。 我们定义函数 f(l,r)(1≤l,r≤n) ，表示序列的子串[l,r]各项的“或”和： al|al+1|⋯|ar 。 Polycarpus在纸上写下了所有的 f(l,r) 的值，他想知道他写下了多少个不同的值。

输入

第一行1个整数 n(1≤n≤105) ，表示序列a的元素个数。 第二行n个整数，表示序列各项元素 ai(0≤ai≤106) 。

输出

输出 f(l,r) 有多少个不同的值。

样例

input

3 1 2 0

output

4

input

10 1 2 3 4 5 6 1 2 9 10

output

11

Note

第一个样例中：6个 f(l,r) 分别为： f(1,1)= 1,f(1, 2) = 3,f(1, 3) = 3,f(2, 2) = 2,f(2, 3) = 2,f(3, 3) = 0 。有4种不同的值：0, 1, 2, 3.

代码

#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <vector> #include <list> #include <map> #include <set> #include <queue> #include <functional> #include <utility> typedef long long ll; const int inf = 0x7ffffff; #define FILENAME "or" #define FOR(i,j,k) for(i=j;i<=k;++i) #define rep(i,j,k) for(i=j;i<k;++i) #define mem(i,j) memset(i,j,sizeof(i)) #define forEach(i,j) for(typeof(j.begin()) i=j.begin();i!=j.end();++i) int read() { int f = 1, s = 0; char ch = getchar(); for ( ; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = -1; for ( ; '0' <= ch && ch <= '9'; ch = getchar()) s = s * 10 + ch - '0'; return s * f; } namespace Solve { const int N = 100005; int mark[1<<20], a[N]; void solve() { int n = read(), i, x, y, j, ans = 0; FOR(i,1,n) a[i] = read(); FOR(i,1,n) { x = 0; if (!mark[a[i]]) mark[a[i]] = 1, ++ans; for (j = i - 1; j; --j) { x |= a[j]; if (!mark[x | a[i]]) mark[x | a[i]] = 1, ++ans; if ((x | a[i]) == x) break; } } printf("%d", ans); } } int main() { freopen(FILENAME".in","r",stdin); freopen(FILENAME".out","w",stdout); Solve::solve(); return 0; }