← 返回题目列表

Codeforces · 1609/F

F. 有趣的部分

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

William 有一个非负数数组 $$$a_1, a_2, \dots, a_n$$$。他想让你找出有多少段 $$$l \le r$$$ 通过了检查。检查按以下方式进行:

1. 在从 $$$l$$$ 开始到 $$$r$$$ 结束的数组段上找到最小和最大数字。
2. 如果最小和最大数的二进制表示具有相同的位数等于 1,则认为检查通过。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$),数组 $$$a$$$ 的大小。

第二行包含$$$n$$$整数$$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{18}$$$),数组$$$a$$$的内容。

输出

输出一个数字——通过检查的段总数。

示例

输入 #1

5
1 2 3 4 5

输出 #1

9

输入 #2

10
0 5 7 3 9 10 1 6 13 7

输出 #2

18