First, consider the case you choose \(M = 2\).
\(x \bmod{2}\) is \(1\) if \(x\) is odd and \(0\) if \(x\) is even, so every element in \(A\) becomes \(0\) or \(1\). Thus, there will be at most two different elements in \(A\).

Therefore, the answer is at most \(2\). Now, let us try to find the answer as follows.

• In some way, check if there is an \(M\) that makes the number of different elements \(1\).
• If there is such an \(M\), the answer is \(1\); otherwise, it is \(2\).

To make this check easier, let us rephrase the condition “the number of different elements becomes \(1\)” into the following:

• \(A_1\) and \(A_2\) become the same,
  \(A_2\) and \(A_3\) become the same,
  \(\vdots\),
  and
  \(A_{N-1}\) and \(A_N\) become the same after the operation.

For what \(M\) will \(A_{i}\) and \(A_{i+1}\) match? It is an \(M\) such that the remainder when \(A_i\) is divided by \(M\) equals the remainder when \(A_{i+1}\) is divided by \(M\), which is the same as an \(M\) such that \(A_i - A_{i+1}\) is divisible by \(M\).

Thus, there is an \(M\) that makes the number of different elements \(1\) if and only if:

• there is an \(M\) that divides all of \(A_1 - A_2, A_2 - A_3, \dots, A_{N-1} - A_N\).

We can check this fast using the notion of the greatest common divisor. Let \(g = \gcd(\lbrace \vert A_1-A_2 \vert, \vert A_2-A_3 \vert, \dots, \vert A_{N-1}-A_N \vert \rbrace)\).

• If \(g=0\):

In this case, the following holds for all \(i\):

\[\vert A_i-A_{i+1} \vert = 0 \iff A_i = A_{i+1}.\]

Thus, the number of different elements is already \(1\) before the operation, so it will remain \(1\) no matter what \(M\) is chosen.

• If \(g=1\):

Assume for contradiction that there is a positive integer \(x\) such that choosing \(M=x\) makes the number of different elements \(1\). Then, every \(\vert A_i - A_{i+1} \vert\) should be divisible by \(x\), so \(g\) should be a multiple of \(x\), contradicting with \(g=1\).
Therefore, there is no \(M\) satisfying the condition.

• If \(g \geq 2\):

Choosing \(M=g\) makes all elements in \(A\) the same.

Now that we can check if there is an \(M\) that makes the number of different elements \(1\), the problem is solved fast enough in \(\mathrm{O}(N \log \max(A))\) time.

• Sample Implementation(PyPy)

import math
N = int(input())
A = list(map(int, input().split()))
g = 0
for i in range(N - 1):
  g = math.gcd(g, abs(A[i] - A[i + 1]))
print(2 if g == 1 else 1)