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