[AGC043B] 123 Triangle

- 给出一个长度为 $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\}$。

[problemUrl]: https://atcoder.jp/contests/agc043/tasks/agc043_b 各要素が $ 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} $ を出力せよ。

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 $ です。