Description

给定一个长度为 $N$ 的序列，第$i$个位置的权值为$a_i$，从序列中任意选出两个不同的位置 $i,j(i<j)$，定义$(i,j)$异或和为 $a_i\oplus a_{i+1}...\oplus a_j$，求所有点对 $(i,j)$ 的异或和是是多少。

Input

第一行输入一个整数 $N$，代表序列元素个数。
第二行 $N$ 个整数，代表序列中每个数的值。

Output

输出一个整数，代表所有点对的异或和。

Sample Input

2
1 2

Sample Output

3

Limitation

1s, 1024KiB for each test case.

Hint

对于样例来说，只有一对点对 $(1,2)$，因此答案为 $1$ 与 $2$ 的异或值 $3$。
40%: N <= 1000
100%: N <= 100000
100%: a[i] <= 1e9

Source

by - shellpicker