#y1015. sequence1

sequence1

Description

有一个 n×nn\times n 的二维数组 aa。当 1≤i<n,1≤j≤i1\leq i\lt n,1\leq j \leq i 时,ai,j=ai+1,j⊕ai+1,j+1a_{i,j}=a_{i+1,j}\oplus a_{i+1,j+1}。

其中,⊕\oplus 表示异或。

现在告诉你 an,1an,2…an,na_{n,1}a_{n,2}\dots a_{n,n},请求出 ∑i=1nai,1\sum\limits_{i=1}^{n}a_{i,1}。

Format

Input

第一行一个整数 nn。

第二行 nn 个整数 an,1an,2…an,na_{n,1}a_{n,2}\dots a_{n,n}。

Output

一行,如题。

Samples

5
1 0 1 1 0
4

Limitation

对于样例:

11

1 01\ 0

0 1 10\ 1\ 1

1 1 0 11\ 1\ 0\ 1

1 0 1 1 01\ 0\ 1\ 1\ 0

1+1+0+1+1=41+1+0+1+1=4

n⩽106n\leqslant 10^6

ai⩽109a_i\leqslant10^9

相关

在下列比赛中:

ACM