Solution

Two numbers have the same remainder modulo $d$ if and only if their difference is divisible by $d$. Thus, for a fixed sequence, the largest suitable $d$ is the greatest common divisor of consecutive differences. Every other pairwise difference is also divisible by this gcd because it is a sum of consecutive differences.

Let a_i=x_{i+1}-x_i for 1 \le i < n. Build two arrays:

• p_i is the gcd of a_1, a_2, \ldots, a_i, with p_0=0;

• s_i is the gcd of a_i, a_{i+1}, \ldots, a_{n-1}, with s_n=0.

Consider removing elements from $l$ through r=l+k-1. The consecutive differences in the remaining sequence consist of three parts:

• differences within the left part, with gcd p_{l-2} if l>1;

• differences within the right part, with gcd s_{r+1} if r<n;

• one new difference x_{r+1}-x_{l-1} if both l>1 and r<n.

Ignore any missing parts. Start the gcd calculation at zero, using the fact that the gcd of zero and a positive integer is that integer.

Try all n-k+1 values of $l$. For each, find the gcd of the listed values and take the largest result. The new difference between the two parts is computed directly from two sequence elements.

Correctness proof

For each removal, the algorithm considers every consecutive difference in the remaining sequence: unchanged differences on the left and right, and the difference joining the two parts when both are non-empty. There are no other consecutive pairs after the removal.

The gcd of these differences divides every pairwise difference, so all remaining numbers have the same remainder modulo this gcd. Conversely, any suitable $d$ must divide every consecutive difference and therefore cannot exceed their gcd.

Thus, the algorithm finds the largest suitable $d$ for each removal. Since it tries every allowed removal, the largest result is the required answer.

Complexity

The time complexity is O(n \log c), where c \le 2 \cdot 10^9 is the largest possible difference between two input numbers. The extra space is $O(n)$.