C. Sasha and a Bit of Relax

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Sasha likes programming. Once, during a very long contest, Sasha decided that he was a bit tired and needed to relax. So he did. But since Sasha isn't an ordinary guy, he prefers to relax unusually. During leisure time Sasha likes to upsolve unsolved problems because upsolving is very useful.

Therefore, Sasha decided to upsolve the following problem:

You have an array aa with nn integers. You need to count the number of funny pairs (l,r)(l,r) (l≤r)(l≤r) . To check if a pair (l,r)(l,r) is a funny pair, take mid=l+r−12mid=l+r−12 , then if r−l+1r−l+1 is an even number and al⊕al+1⊕…⊕amid=amid+1⊕amid+2⊕…⊕aral⊕al+1⊕…⊕amid=amid+1⊕amid+2⊕…⊕ar , then the pair is funny. In other words, ⊕⊕ of elements of the left half of the subarray from ll to rr should be equal to ⊕⊕ of elements of the right half. Note that ⊕⊕ denotes the bitwise XOR operation.

It is time to continue solving the contest, so Sasha asked you to solve this task.

Input

The first line contains one integer nn (2≤n≤3⋅1052≤n≤3⋅105 ) — the size of the array.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai<2200≤ai<220 ) — array itself.

Output

Print one integer — the number of funny pairs. You should consider only pairs where r−l+1r−l+1 is even number.

Examples

Input

Copy

5
1 2 3 4 5

Output

Copy

1

Input

Copy

6
3 2 2 3 7 6

Output

Copy

3

Input

Copy

3
42 4 2

Output

Copy

0

Note

Be as cool as Sasha, upsolve problems!

In the first example, the only funny pair is (2,5)(2,5) , as 2⊕3=4⊕5=12⊕3=4⊕5=1 .

In the second example, funny pairs are (2,3)(2,3) , (1,4)(1,4) , and (3,6)(3,6) .

In the third example, there are no funny pairs.

 

给出一个数组，求在这个数组中有多少个符合要求的区间。要求如下：设区间为(l,r)

l+r-1为偶数
al⊕al+1⊕…⊕amid=amid+1⊕amid+2⊕…⊕ar

首先说明XOR运算
1 XOR 1=0 |    0 XOR 0=0
1 XOR 0=1 |   0 XOR 1=1
且XOR满足运算的


交换律
a ^ b = b ^ a
1


结合律
a ^ (b ^ c) = (a ^ b) ^ c
1


分配率
a ^ (b+c) = a ^ b + a ^ c
1


自反
a ^ b ^ b = a ^ 0 = a
1

看到这个自反性，就应该会了吧


利用自反的性质，可以实现一些小操作(与题目无关)，如
交换两个数 ： a=a ^ b;  b=a ^ b; a=a ^ b;
判断两个数是否相等： a ^ b ==0
回到正题，记
XOR(al,ar)表示 al⊕al+1⊕…⊕amid⊕amid+1⊕amid+2⊕…⊕ar
由异或性质不难得出 A ^ B = C,A = B ^ C
故判断条件可进一步写为
0⊕al⊕al+1⊕…⊕amid=amid+1⊕amid+2⊕…⊕ar
0=al⊕al+1⊕…⊕amid⊕amid+1⊕amid+2⊕…⊕ar
0=XOR(al,ar)
这样得出一个结论，若在区间(l,r)上XOR(al,ar）=0，则对于任意的 i 属于区间(l,r) (包括区间端点) ,有XOR(al,ai)==XOR(ai+1,ar)
Ps:如有错误还请指正
记product[i] 表示 XOR(a0,ai),根据异或自反的性质，条件 0=XOR(al,ar) 可变为product[l-1] == product[r]。
由此得知，首先要预处理所给数组，得出product[]
此外，题目中另一个要求为 l+r-1 为偶数。所以l，r不能同奇偶，(l-1)，r一定同奇偶。
所以，现在只需要找出有多少同奇偶位置上product[]相同的位置，即当 i%2==j%2 (i<j)时，满足条件product[i] == product[j]的数对(i,j)有多少对
 

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
const int txt=2e6;
int a[maxn];
int sum[maxn];
int v1[txt];
int v2[txt];
int main()
{

    memset(sum,0,sizeof(sum));
    int n;
    scanf("%d",&n);
    sum[0]=0;
    memset(v1,0,sizeof(v1));
    memset(v2,0,sizeof(v2));
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]^a[i];
    }
    long long ans=0;
    for(int i=0;i<=n;i++)//是偶数分奇偶
    {
        if(i&1)
        {
            ans+=v1[sum[i]];
            v1[sum[i]]++;
        }
        else
        {
             ans+=v2[sum[i]];
             v2[sum[i]]++;
        }

    }
    cout<<ans;
}