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