AT_agc043_b [AGC043B] 123 Triangle

给定一个长度为 $ 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} $ 的值。

#### 【数据范围】 - $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$。