AT_agc043_b [AGC043B] 123 Triangle

[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} $ を出力せよ。

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