English · Original
Chinese · Translation
Formal · Original
_Disclaimer: there are lots of untranslateable puns in the Russian version of the statement, so there is one more reason for you to learn Russian :)_
Rick and Morty like to go to the ridge High Cry for crying loudly — there is an extraordinary echo. Recently they discovered an interesting acoustic characteristic of this ridge: if Rick and Morty begin crying simultaneously from different mountains, their cry would be heard between these mountains up to the height equal the bitwise OR of mountains they've climbed and all the mountains between them.
Bitwise OR is a binary operation which is determined the following way. Consider representation of numbers _x_ and _y_ in binary numeric system (probably with leading zeroes) _x_ = _x__k_... _x_1_x_0 and _y_ = _y__k_... _y_1_y_0. Then _z_ = _x_ | _y_ is defined following way: _z_ = _z__k_... _z_1_z_0, where _z__i_ = 1, if _x__i_ = 1 or _y__i_ = 1, and _z__i_ = 0 otherwise. In the other words, digit of bitwise OR of two numbers equals zero if and only if digits at corresponding positions is both numbers equals zero. For example bitwise OR of numbers 10 = 10102 and 9 = 10012 equals 11 = 10112. In programming languages C/C++/Java/Python this operation is defined as «_|_», and in Pascal as «_or_».
Help Rick and Morty calculate the number of ways they can select two mountains in such a way that if they start crying from these mountains their cry will be heard above these mountains and all mountains between them. More formally you should find number of pairs _l_ and _r_ (1 ≤ _l_ < _r_ ≤ _n_) such that bitwise OR of heights of all mountains between _l_ and _r_ (inclusive) is larger than the height of any mountain at this interval.
## Input
The first line contains integer _n_ (1 ≤ _n_ ≤ 200 000), the number of mountains in the ridge.
Second line contains _n_ integers _a__i_ (0 ≤ _a__i_ ≤ 109), the heights of mountains in order they are located in the ridge.
## Output
Print the only integer, the number of ways to choose two different mountains.
[samples]
## Note
In the first test case all the ways are pairs of mountains with the numbers (numbering from one):
<center>(1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)</center>In the second test case there are no such pairs because for any pair of mountains the height of cry from them is 3, and this height is equal to the height of any mountain.
_免责声明：俄语版本的题面中包含大量无法翻译的双关语，因此这也是你学习俄语的另一个理由 :)_
里克和莫蒂喜欢去高鸣岭大声哭喊——那里有一个非凡的回声。最近，他们发现这个山岭有一个有趣的声学特性：如果里克和莫蒂从不同的山峰同时开始哭喊，他们的哭声会在这些山峰之间传播，直到达到一个高度，该高度等于他们所攀登的山峰以及它们之间所有山峰高度的按位或。
按位或是一种二进制运算，其定义如下：考虑数字 #cf_span[x] 和 #cf_span[y] 的二进制表示（可能带有前导零）#cf_span[x = xk... x1x0] 和 #cf_span[y = yk... y1y0]。那么 #cf_span[z = x | y] 定义为：#cf_span[z = zk... z1z0]，其中 #cf_span[zi = 1] 当且仅当 #cf_span[xi = 1] 或 #cf_span[yi = 1]，否则 #cf_span[zi = 0]。换句话说，两个数的按位或的某一位为零，当且仅当这两个数在对应位置上的位都为零。例如，数字 #cf_span[10 = 10102] 和 #cf_span[9 = 10012] 的按位或等于 #cf_span[11 = 10112]。在 C/C++/Java/Python 编程语言中，该运算定义为 «_|_»，在 Pascal 中定义为 «_or_»。
帮助里克和莫蒂计算他们可以选择两座山峰的方式数，使得当他们从这两座山峰开始哭喊时，他们的哭声会高于这些山峰以及它们之间所有的山峰。更正式地说，你需要找出满足以下条件的配对 #cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ l < r ≤ n]）的数量：区间 [#cf_span[l], #cf_span[r]] 内所有山峰高度的按位或，大于该区间内任意一座山峰的高度。
第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]），表示山岭中的山峰数量。
第二行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[0 ≤ ai ≤ 10^9]），表示山峰按顺序排列的高度。
请输出一个整数，表示选择两座不同山峰的方式数。
在第一个测试用例中，所有合法的配对是山峰编号（从1开始编号）：
在第二个测试用例中，不存在这样的配对，因为对于任意一对山峰，他们的哭声高度为 #cf_span[3]，且该高度等于任意一座山峰的高度。
## Input
第一行包含整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]），表示山岭中的山峰数量。
第二行包含 #cf_span[n] 个整数 #cf_span[ai]（#cf_span[0 ≤ ai ≤ 10^9]），表示山峰按顺序排列的高度。
## Output
请输出一个整数，表示选择两座不同山峰的方式数。
[samples]
## Note
在第一个测试用例中，所有合法的配对是山峰编号（从1开始编号）：#cf_span[(1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]
在第二个测试用例中，不存在这样的配对，因为对于任意一对山峰，他们的哭声高度为 #cf_span[3]，且该高度等于任意一座山峰的高度。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of mountains.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of non-negative integers representing mountain heights.
**Constraints**
$ 1 \leq n \leq 200{,}000 $,
$ 0 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $.
**Objective**
Count the number of pairs $ (l, r) $ such that $ 1 \leq l < r \leq n $ and
$$
\bigvee_{i=l}^{r} a_i > \max_{i=l}^{r} a_i,
$$
where $ \bigvee $ denotes the bitwise OR over the interval $ [l, r] $.
API Response (JSON)
{
"problem": {
"name": "D. High Cry",
"description": {
"content": "_Disclaimer: there are lots of untranslateable puns in the Russian version of the statement, so there is one more reason for you to learn Russian :)_ Rick and Morty like to go to the ridge High Cry f",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF875D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "_Disclaimer: there are lots of untranslateable puns in the Russian version of the statement, so there is one more reason for you to learn Russian :)_\n\nRick and Morty like to go to the ridge High Cry f...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "_免责声明：俄语版本的题面中包含大量无法翻译的双关语，因此这也是你学习俄语的另一个理由 :)_\n\n里克和莫蒂喜欢去高鸣岭大声哭喊——那里有一个非凡的回声。最近，他们发现这个山岭有一个有趣的声学特性：如果里克和莫蒂从不同的山峰同时开始哭喊，他们的哭声会在这些山峰之间传播，直到达到一个高度，该高度等于他们所攀登的山峰以及它们之间所有山峰高度的按位或。\n\n按位或是一种二进制运算，其定义如下：考虑数字 #...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of mountains. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of non-negative integers representing mountain heights.\n\n**Constraints** \n$...",
"is_translate": false,
"language": "Formal"
}
]
}