Vasya 有一个序列 $$$a$$$,由 $$$n$$$ 整数 $$$a_1、a_2、\dots、a_n$$$ 组成。 Vasya 可以执行以下操作:从序列中选择一些数字并交换其二进制表示中的任何位对。例如,Vasya 可以将数字 $$$6$$$ $$$(\dots 00000000110_2)$$$ 转换为 $$$3$$$ $$$(\dots 00000000011_2)$$$, $$$12$$$ $$$(\dots 000000001100_2)$$$, $$$1026$$$ $$$(\dots 10000000010_2)$$$ 等等。 Vasya 可以对序列中的任何数字使用此操作任意(可能为零)次。
Vasya 称一个序列为好序列,如果使用上述操作,他可以获得所有等于 $$$0$$$ 的元素按位异或的序列。
对于给定的序列 $$$a_1, a_2, \ldots, a_n$$$ Vasya 希望计算整数对 $$$(l, r)$$$ 的数量,使得 $$$1 \le l \le r \le n$$$ 和序列 $$$a_l, a_{l + 1}, \dots, a_r$$$ 很好。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 序列的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — 序列 $$$a$$$。
输出
打印一个整数 - $$$(l, r)$$$ 的对数,使得 $$$1 \le l \le r \le n$$$ 和序列 $$$a_l, a_{l + 1}, \dots, a_r$$$ 很好。
示例
输入 #1
3 6 7 14
输出 #1
2
输入 #2
4 1 2 1 16
输出 #2
4
注意
在第一个示例中,$$$(2, 3)$$$ 和 $$$(1, 3)$$$ 是有效的。 $$$(2, 3)$$$ 有效,因为 $$$a_2 = 7 \rightarrow 11$$$、$$$a_3 = 14 \rightarrow 11$$$ 和 $$$11 \oplus 11 = 0$$$,其中 $$$\oplus$$$ — 按位异或。 $$$(1, 3)$$$ 对有效,因为 $$$a_1 = 6 \rightarrow 3$$$、$$$a_2 = 7 \rightarrow 13$$$、$$$a_3 = 14 \rightarrow 14$$$ 和 $$$3 \oplus 13 \oplus 14 = 0$$$。
在第二个示例中,$$$(1, 2)$$$、$$$(2, 3)$$$、$$$(3, 4)$$$ 和 $$$(1, 4)$$$ 是有效的。