← 返回题目列表

Codeforces · 875/D

D. 高哭

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

免责声明:该声明的俄语版本中有很多无法翻译的双关语,因此您又多了一个学习俄语的理由:)

瑞克和莫蒂喜欢去山脊High Cry大声哭泣——那里有非凡的回声。最近,他们发现了这个山脊的一个有趣的声学特征:如果瑞克和莫蒂开始同时从不同的山上哭泣,他们的哭声会在这些山之间听到,直到高度等于他们爬过的山和它们之间的所有山的按位或。

按位或是一种二元运算,其确定方式如下。考虑二进制数字系统中数字 x 和 y 的表示(可能带有前导零)x = xk...x1x0 和 y = yk...y1y0。那么 z = x | y 的定义方式如下:z = zk...z1z0,其中 zi = 1(如果 xi = 1 或 yi = 1),否则 zi = 0。换句话说,当且仅当两个数字的相应位置上的数字都等于0时,两个数字按位或的数字才等于0。例如,数字 10 = 10102 和 9 = 10012 的按位或等于 11 = 10112。在编程语言 C/C++/Java/Python 中,此运算定义为“|”,在 Pascal 中定义为“or”。

帮助瑞克和莫蒂计算他们可以选择两座山的方式的数量,以便如果他们开始从这些山上哭泣,他们的哭声将会在这些山以及它们之间的所有山上听到。更正式地说,您应该找到 l 和 r 对的数量 (1 ≤ l < r ≤ n),使得 l 和 r(含)之间所有山的高度的按位或大于此间隔内任何山的高度。

输入

第一行包含整数 n (1 ≤ n ≤ 200 000),即山脊中的山脉数量。

第二行包含 n 个整数 ai (0 ≤ ai ≤ 109),即山脉的高度(按它们位于山脊的顺序排列)。

输出

打印唯一的整数,选择两座不同山峰的数量。

示例

输入 #1

5
3 2 1 6 5

输出 #1

8

输入 #2

4
3 3 3 3

输出 #2

0

注意

在第一个测试用例中,所有道路都是带有数字的山对(从一开始编号):

(1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)

在第二个测试用例中,没有这样的对,因为对于任何一对山,它们的哭声高度都是 3,并且这个高度等于任何山的高度。