题目描述

各要素が $1$ か $2$ か $3$ である長さ $N$ の数字列 $a_1a_2\ldots\ a_N$ が与えられます。 $x_{i,j}$ を次のように定義します。

• $x_{1,j}\ :=\ a_j$ $\quad$ ($1\ \leq\ j\ \leq\ N$)
• $x_{i,j}\ :=\ |\ x_{i-1,j}\ -\ x_{i-1,j+1}\ |$ $\quad$ ($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}$ を出力せよ。

题目大意

• 给出一个长度为 $N$ 的，仅包含 123 的序列 $a$。 （以字符串形式给出）
• 设有递推关系：$f_{k, x}=| f_{k-1,x} - f_{k-1,x+1} | (k > 1)$，特别的，对于 $k=1$，有 $f(1,x) = a_x$。
• 请你求出 $f_{N, 1}$。
• $1 \leq N \leq 10^6$，$a_i \in \{1, 2, 3\}$。

4
1231

1

10
2311312312

0

提示

制約

• $2\ ≦\ N\ ≦\ 10^6$
• $a_i\ =\ 1,2,3$ $(1\ \leq\ i\ \leq\ N)$

Sample Explanation 1

$x_{1,1},x_{1,2},x_{1,3},x_{1,4}$ はそれぞれ、$1,2,3,1$ です。 $x_{2,1},x_{2,2},x_{2,3}$ はそれぞれ、$|1-2|\ =\ 1,|2-3|\ =\ 1,|3-1|\ =\ 2$ です。 $x_{3,1},x_{3,2}$ はそれぞれ、$|1-1|\ =\ 0,|1-2|\ =\ 1$ です。 最後に、 $x_{4,1}\ =\ |0-1|\ =\ 1$ なので、答えは $1$ です。