Pavel 正在向他的朋友 Egor 发送一个非负整数数组。他希望确保在数组到达朋友手中之前没有人对其进行篡改。为了解决这个问题，Pavel 需要为他的数组计算某种校验和或摘要。Pavel 很有创新精神，他发明了以下算法来计算数组的摘要：统计满足“子数组中所有数字的按位异或（bitwise xor）结果等于该子数组中所有数字的按位与（bitwise and）结果”的子数组数量。

例如，考虑一个包含四个二进制数 “01”、“10”、“11” 和 “11” 的数组。下表左侧列出了该数组每个子数组的按位异或结果，右侧列出了该数组每个子数组的按位与结果。表格的行对应子数组的起始元素（从数组的第 1 个元素到第 4 个元素），列对应子数组的结束元素。匹配的值以灰色背景突出显示。

你的任务是帮助 Pavel 计算给定数组的这种摘要。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)。第二行包含 $n$ 个非负整数 $a_i$ ($0 \le a_i \le 2^{31} - 1$)，以十进制表示。

输出格式

在第一行输出 Pavel 计算出的给定数组的摘要。

样例

输入 1

4
1 2 3 3

输出 1

6

说明 1

上述样例输入对应于题目描述中的示例。