The sequence \(A\) obtained by the operations satisfies \(A_i=|A_{i+1}-A_{i+2}|\). Therefore, once \(A_N\) and \(A_{N-1}\) are determined, all elements are uniquely determined in order from the back.

We enumerate all \(A_{N-1}\) and find \(A_1, A_2\) for each.

Using the same approach as the Euclidean algorithm, we can find the value of \(A_1\) in \(O(\log \min (A_N,A_{N-1}))\). (Proof below)

Therefore, this problem can be solved in \(O(M \log M)\).

Proof

Assume \(A_N \ge A_{N-1}\). If \(A_N < A_{N-1}\), we find \(A_{N-2}\) first and then apply the same reasoning to \(A_{N-1}\) and \(A_{N-2}\).

Let \(A_N = x\) and \(A_{N-1} = y\).

When \(x=y\) or \(y=0\), the sequence continues like \(A = (\ldots,0,x,x,0,x,x)\), so \(A_1\) can be easily found.

Below, we assume \(x>y>0\).

Let \(x = yq + r\) \((q = \lfloor x/y\rfloor, 0 \leq r < y)\).

When \(q\) is even, let \(q=2t\), then \((A_{N-3t}, A_{N-3t-1}) = (r, y)\).
This is because if \(x>2y\), then in three steps we have \((x,y) \rightarrow (y,x-y) \rightarrow(x-y,x-2y) \rightarrow(x-2y, y)\).

When \(q\) is odd, let \(q=2t+1\), then \((A_{N-3t-1}, A_{N-3t-2}) = ( y,r)\).

Since we can replace \((x,y) \rightarrow (y,r)\) or \((r,y)\) in \(O(1)\) steps, we can compute \(A_1\) in \(O(\log y)\) using the same approach as the Euclidean algorithm.