Hyper Dice Rolling

In $N$-dimensional Euclidean space, an $N$-dimensional Cartesian coordinate system is defined. It has $N$ coordinate axes through the origin. In this problem, the $i$-th axis is called the $x_i$ axis. The direction in which $x_i$ increases is the $+x_i$ direction, and the direction in which $x_i$ decreases is the $-x_i$ direction.

All points with $x_1 \leq -\tfrac{1}{2}$ are filled. For convenience, the part with $x_1 < -\tfrac{1}{2}$ is called the floor, and the hyperplane $x_1 = -\tfrac{1}{2}$ is called the floor surface. A die of size $1 \times 1 \times \cdots \times 1$ is centered at the origin. That is, the die occupies $[-\tfrac{1}{2}, \tfrac{1}{2}] \times [-\tfrac{1}{2}, \tfrac{1}{2}] \times \cdots \times [-\tfrac{1}{2}, \tfrac{1}{2}]$. The die has $2N$ faces, each an $(N-1)$-dimensional figure. For each integer $i$ with $1 \leq i \leq N$, the face in the $+x_i$ direction is labeled $2N+1-i$, and the face in the $-x_i$ direction is labeled $i$.

You are given $M$ commands. After performing all commands in order, find the squared Euclidean distance between the origin and the center of the die. Each command is an integer $v$ with $1 \leq v \leq 2N$. It means to roll the die so that the face labeled $v$ lies on the floor surface. It is guaranteed that $v$ is not labeled on the $-x_1$ or $+x_1$ face before the roll.

The first line contains two positive integers $N$ and $M$. $N$ is the number of dimensions of the die, and $M$ is the number of rolling commands. ($3 \leq N \leq 10^9$, $1 \leq M \leq 500\,000$)

The next line contains $M$ positive integers $v_1, v_2, \cdots, v_M$. $v_i$ is the integer for the $i$-th command. ($1 \leq v_i \leq 2N$)

On the first line, print the squared Euclidean distance between the origin and the center of the die after performing all commands in order, as an integer.

The squared Euclidean distance between two points $(x_1, x_2, \cdots, x_N)$ and $(y_1, y_2, \cdots, y_N)$ in $N$-dimensional Euclidean space is

$(x_1-y_1)^2 + (x_2-y_2)^2 + \cdots + (x_N-y_N)^2$

The exact definition of rolling the die is as follows. Let $V$ be the face of the die labeled $v$, and let $W$ be the face of the die touching the floor. The intersection $Z$ of $V$ and $W$ is an $(N-2)$-dimensional figure. Rolling the die so that $V$ lies on the floor surface means rotating the die 90 degrees clockwise or counterclockwise about $Z$. The rotation direction must be one in which the die does not go into the floor.

Rotating the die by $\theta$ degrees about the $(N-2)$-dimensional figure $Z$ is defined as follows. Let $x$ be any point inside the die. Let $A$ be the space that passes through $x$ and is linearly independent of $Z$. Since $Z$ is $(N-2)$-dimensional, $A$ is always a 2-dimensional infinite plane. Let $y$ be the intersection of $A$ and $Z$. Since $A$ and $Z$ are linearly independent, $y$ is a single point. Within the plane $A$, rotate $x$ by $\theta$ degrees about $y$. Doing this for every $x$ is defined as rotating the die by $\theta$ degrees.