まず、操作で \(M = 2\) を選ぶ場合を考えてみましょう。
\(x \bmod{2}\) は \(x\) が奇数の場合は \(1\), 偶数の場合は \(0\) なので、操作によって \(A\) の要素はすべて \(0\) か \(1\) のどちらかに変化します。よってこのとき \(A\) に含まれる要素の種類数は \(2\) 種類以下となります。

よって、答えは大きくとも \(2\) 以下です。そこで、次のような手順で答えを求めることを考えてみましょう。

• なんらかの方法で「種類数が \(1\) 種類になるような \(M\) が存在するか？」を調べる。
• そのような \(M\) が存在すれば \(1\) が答えとなる。逆に、存在しない場合は \(2\) が答えとなる。

このような手順を考えることで、この問題は 「種類数が \(1\) 種類になるような \(M\) が存在するか？」という判定問題に言い換えられることができます。

この条件を判定する方法を考えてみましょう。
「種類数が \(1\) 種類になる」というのを処理しやすいように言い換えると次のようになります。

• 「操作後に \(A_1\) と \(A_2\) が一致する」かつ
  「操作後に \(A_2\) と \(A_3\) が一致する」かつ
  \(\vdots\)
  「操作後に \(A_{N-1}\) と \(A_N\) が一致する」

操作後の \(A_{i}\) と \(A_{i+1}\) が一致するような \(M\) の条件を考えましょう。このような \(M\) は、すなわち「\(A_i\) を \(M\) で割ったあまりと、\(A_{i+1}\) を \(M\) で割ったあまりが一致するような \(M\) 」で、これは「\(A_i - A_{i+1}\) が \(M\) で割り切れるような \(M\) 」に等しいです。
よって「種類数が \(1\) 種類になるような \(M\) が存在するか？」という命題は次の命題と同値です。

• \(A_1 - A_2, A_2 - A_3, \dots, A_{N-1} - A_N\) をすべて割り切る \(M\) は存在するか？

この問題は最大公約数の考え方を用いれば高速に判定できます。すなわち、\(g = \gcd(\lbrace \vert A_1-A_2 \vert, \vert A_2-A_3 \vert, \dots, \vert A_{N-1}-A_N \vert \rbrace)\) として、\(g\) の値によって次のように場合分け出来ます。

• \(g=0\) の場合

\(g=0\) の場合、すべての \(i\) で

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

が成り立っているので、操作を行う前の時点で種類数が \(1\) 種類です。よってどのような \(M\) を選んでも操作後の種類数は \(1\) 種類のままです。

• \(g=1\) の場合

背理法で示します。ある正整数 \(x\) が存在して、 \(M=x\) として種類数を \(1\) 種類にできるならば、\(\vert A_i - A_{i+1} \vert\) はすべて \(x\) で割り切れるはずなので、\(g\) は \(x\) の倍数になります。しかし \(g=1\) なので矛盾します。
よって条件を満たす \(M\) は存在しないことがわかります。

• \(g \geq 2\) の場合

\(M=g\) とすれば \(A\) の要素をすべて一致させられます。

以上の方法で「種類数が \(1\) 種類になるような \(M\) が存在するか？」という判定問題を解くことができたので、これをもとに前述の手順を用いればこの問題を十分高速に解くことができます。計算量は \(\mathrm{O}(N \log \max(A))\) です。

• 実装例(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)