Blackslex and Number Theory

Let the smallest value be

$m = \min(a_1,a_2,\ldots,a_n).$

Modulo operations never increase a number. So whatever common value we finish with, it cannot be bigger than $m$.

That gives us the first important baseline.

For any

$k \le m,$

we can make every element equal to $0$: for each $a_i$, choose

$x=a_i.$

This is allowed because $a_i \ge m \ge k$, and

$a_i \bmod a_i = 0.$

So the answer is at least $m$. Free points. Take them.

What changes when $k>m$?

If $k>m$, then the smallest element $m$ is stuck forever. Every allowed modulus satisfies $x \ge k > m$, so

$m \bmod x = m.$

Therefore, if $k>m$, the final common value must be exactly $m$.

Now every other value $v>m$ must be reducible to $m$.

Look at the final operation that turns this element into $m$. Suppose the value right before that operation is $u$. Since values only decrease,

$u \le v.$

For some modulus $x \ge k$, we need

$u \bmod x = m.$

That means

$u = qx + m$

for some positive integer $q$, so

$x \mid (u-m)$

and in particular

$x \le u-m \le v-m.$

Since $k \le x$, we get the necessary condition

$k \le v-m.$

This has to hold for every non-minimum element. The tightest one is the second smallest element.

After sorting:

$a_0=m, \qquad a_1=\text{second smallest value}.$

So any answer bigger than $m$ must satisfy

$k \le a_1-m.$

Can we achieve that upper bound? Yes, if it is actually bigger than $m$.

Set

$k=a_1-m.$

For every other value $v$, we have

$v-m \ge a_1-m = k.$

Choose

$x=v-m.$

Because $k>m$, this modulus is larger than $m$, and

$v \bmod (v-m)=m.$

So every element becomes $m$, while the minimum stays $m$.

If $a_1-m \le m$, then we cannot beat the baseline $m$, but $m$ still works by sending everything to $0$.

Therefore the answer is

$\boxed{\max(a_0, a_1-a_0)}.$

Sort the array, read the two smallest numbers, print that value. Number theory showed up, made one divisibility observation, and left before things got annoying.

Complexity: sorting costs $O(n\log n)$ per test case, and the total $n$ is bounded by $2\cdot 10^5$, so this easily fits.