← 返回题目列表

Codeforces · 243/A

A. 全新功能

中文机器翻译题面 查看原题

Polycarpus 有一个序列,由 n 个非负整数组成:a1, a2, ..., an。

让我们将序列 a 的函数 f(l, r) (l, r 是整数,1 ≤ l ≤ r ≤ n)定义为索引从 l 到 r 的所有序列元素的按位或运算。形式上:f(l, r) = al | 阿尔 + 1 | ...| ar。

Polycarpus 拿了一张纸,写出了所有 l、r 的函数 f(l, r) 的值(l、r 是整数,1 ≤ l ≤ r ≤ n)。现在他想知道,他最终有多少个不同的值。

帮助 Polycarpus,计算给定序列 a 的函数 f(l, r) 的不同值的数量。

表达式 x | y 表示对数字 x 和 y 进行按位或运算。此操作存在于所有现代编程语言中,例如,在 C++ 和 Java 语言中它被标记为“|”,在 Pascal 中被标记为“or”。

输入

第一行包含整数 n (1 ≤ n ≤ 105) — 序列 a 的元素数量。第二行包含 n 个空格分隔的整数 a1, a2, ..., an (0 ≤ ai ≤ 106) — 序列 a 的元素。

输出

打印单个整数 — 给定序列 a 的函数 f(l, r) 的不同值的数量。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

3
1 2 0

输出 #1

4

输入 #2

10
1 2 3 4 5 6 1 2 9 10

输出 #2

11

注意

在第一个测试用例中,Polycarpus 将在纸上写下 6 个数字: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.