题目描述

给你一个长度为N的数组。

如果一个区间是巧妙的，那么他将满足以下条件：

1.区间的元素个数是2的倍数。

2.将区间从1/2的位置分割为两部分，这两部分的元素异或和相同。

请你统计出所有巧妙子区间的个数。

输入格式

第一行输入一个$N(3 \leq N \leq10^5)$，代表数组的长度。

第二行包含N个整数$a_i(0 \leq a_i < 2^{20})$。

输出格式

输出巧妙的子区间的个数。

样例数据

input

5

1 2 3 4 5

output

1

input

6

3 2 2 3 7 6

output

3

第二个样例的3个巧妙区间分别为

[2,2]、[3,2,2,3]、[2,3,7,6]。

input

3

42 4 2

output

0

数据规模与约定

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$