Original proposer: vwxyz

The remainder when dividing \(A_i\) by \(K\) is invariant by an operation.
Compare the following two sequences:

• the sequence obtained by subtracting \(K\) from \(A_i\)
• the sequence obtained by adding \(K\) to \(A_j\) for all \(j\) except for \(i\)

The relative positions of \(A_i\), and the maximum minus the minimum, are equal between them. Therefore, answer does not change if we allow an operation of choosing \(i\) and subtracting \(K\) from \(A_i\).
We can go further: we may replace \(A_i\) with any integer as long as the remainder divided by \(K\) is invariant.

Fix an \(i\) such that the minimum value of \(A\) is \(A_i\).
Since \(\max(A)-\min(A)\) does not change by subtracting \(K\) from \(A_i\) for \(i=1,2,\dots,N\), we may assume \(0 \leq A_i\lt K\).
Then, we can perform operations to make \(A_i \leq A_j \lt A_i+K\) for all \(j\) between \(1\) and \(N\) except for \(i\). Such an \(A_j\) is unique; this is either the remainder when dividing \(A_j\) by \(K\), or the remainder plus \(K\).
By replacing \(A_j\) with the value satisfying \(A_i \leq A_j \lt A_i+K\) computing \(\max(A)-\min(A)\) for all \(i\), the answer can be obtained.

On its own, it costs \(O(N^2)\) time; however, the following optimization speeds it up to about \(O(N)\):

• Replace each element in \(A\) with the remainder divided by \(K\).
• Sort \(A\) in ascending order.
• Using a deque, perform the following operation \(N\) times: retrieve (and remove) the first element of \(A\), add \(K\) to it, and push the result to the end of \(A\).
• After each operation, compute \(\max(A)-\min(A)\). Report the minimum value among them as the answer.

The first and last elements of \(A\) correspond to the minimum and maximum values in a final \(A\), respectively.