Description

有一个 $n\times n$ 的二维数组 $a$。当 $1\leq i\lt n,1\leq j \leq i$ 时，$a_{i,j}=a_{i+1,j}\oplus a_{i+1,j+1}$。

其中，$\oplus$ 表示异或。

现在告诉你 $a_{n,1}a_{n,2}\dots a_{n,n}$，请求出 $\sum\limits_{i=1}^{n}a_{i,1}$。

Format

Input

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_{n,1}a_{n,2}\dots a_{n,n}$。

Output

一行，如题。

Samples

5
1 0 1 1 0

4

Limitation

对于样例：

$1$

$1\ 0$

$0\ 1\ 1$

$1\ 1\ 0\ 1$

$1\ 0\ 1\ 1\ 0$

$1+1+0+1+1=4$

$n\leqslant 10^6$

$a_i\leqslant10^9$