题目描述

给定一个长度为 $N$ 的数字序列 $a_1a_2\ldots a_N$，其中每个元素为 $1$、$2$ 或 $3$。定义 $x_{i,j}$ 如下：

• $x_{1,j} := a_j (1 \leq j \leq N )$；
• $x\_{i,j} := | x\_{i-1,j} - x\_{i-1,j+1} | (2 \leq i \leq N$ 且 $1 \leq j \leq N+1-i )$。

请计算 $x_{N,1}$ 的值。

输入格式

输入将以如下格式通过标准输入给出：

$N$ $a_1$ $a_2$ $\ldots$ $a_N$

输出格式

输出 $x_{N,1}$ 的值。

样例 1

输入

4
1231

输出

1

样例 2

输入

10
2311312312

输出

0

说明/提示

【数据范围】

• $2 \le N \le 10^6$；
• $a_i \in \{1,2,3\}(1 \le i \le N)$。

【样例解释 1】

给定初始序列 $x_{1,j} = a_j$，其中 $a = [1,2,3,1]$。

计算过程如下： $x_{2,1} = |1-2| = 1$，$x_{2,2} = |2-3| = 1$，$x_{2,3} = |3-1| = 2$，$x_{3,1} = |1-1| = 0$，$x_{3,2} = |1-2| = 1$，$x_{4,1} = |0-1| = 1$。

最终答案为 $1$。