\(x\equiv y(\bmod M) \Leftrightarrow M\mid x-y\).

We call \(A_i\) “is chosen” when \(A_i\) equals to the majority in \(A\) eventually.

Clearly, \(\exist 1\le i\lt n\),such that both \(A_i\) and \(A_{i+1}\) are chosen.

The only special case,for example,is when \(n=7\) and \(a_1,a_3,a_5,a_7\) are chosen.

So we enumerate \(1\le i\lt n\),suppose that \(A_i\) and \(A_{i+1}\) are chosen.

Let \(d=A_{i}-A_{i+1}\), we can see that \(M\mid d\).

if \(M\) is not a prime,then you can choose one of its prime factors \(p\) and replace \(M\) with \(p\).

The only special case is when \(M=2^k\) since you can’t let \(M=2\)。

So we only consider about cases when \(M\) is a prime that \(M\ge 3\) holds , or \(M=4\)。

So we can get all prime factors of \(d\) and check them as \(M\).

Let \(\omega=9\),we can see that we’ll check \(\omega\times (n-1)\) numbers as \(M\) at most since \(2\times 3\times 5\times ... \times 23\times 29>10^9\)。

The check can be done in \(O(N)\) easily.

So we get a \(O(\omega \times n^2)\) solution.

submission：https://atcoder.jp/contests/abc272/submissions/35490545