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