原案:vwxyz

操作の前後で、 \(A_i\) を \(K\) で割った余りは不変です。
以下の \(2\) つの数列を比べます。

• \(A_i\) から \(K\) を引いた数列
• \(i\) 以外の \(j\) に対して、\(A_j\) に \(K\) を足すという操作を行った数列

これらの \(A_i\) の相対的な位置関係は変わず、最大値から最小値を引いた値も変わりません。 よって、\(i\) を選んで \(A_i\) から \(K\) を引くという操作を行ってもよいとしても答えは変わりません。
このとき、\(A_i\) を \(K\) で割った余りが同じような任意の整数に置き換えるという操作に言い換えてもよいことがわかります。

最終的な \(A\) の最小値が \(A_i\) となる \(i\) を固定します。
\(i=1,2,\dots,N\) に対して \(A_i\) から \(K\) を引くという操作を行っても \(\max(A)-\min(A)\) は変わらないため、\(0 \leq A_i\lt K\) としてよいです。
このとき、\(1\) 以上 \(N\) 以下の \(i\) でない整数 \(j\) について、\(A_i \leq A_j \lt A_i+K\) となるように操作を行うことができます。このような \(A_j\) は一意に存在し、\(A_j\) を \(K\) で割った余りか、それに \(K\) を足したものです。
すべての \(i\) について \(A_j\) を \(A_i \leq A_j \lt A_i+K\) となるものに置き換え、\(\max(A)-\min(A)\) を求めると答えを求めることができます。

このままだと \(O(N^2)\) かかってしまいますが、以下のように工夫して実装を行うことで、\(O(N)\) などで求めることができます。

• \(A\) の各要素を \(K\) で割った余りで置き換える
• \(A\) をソートする
• deque などを用い、「\(A\) の先頭の要素を取り出して（\(A\) から削除する）それに \(K\) 足したものを \(A\) の末尾に追加する」という操作を \(N\) 回行う
• 各操作の前後で \(\max(A)-\min(A)\) を求め、最も小さかったものを答えとする

\(A\) の先頭と末尾の要素はそれぞれ最終的な \(A\) での最小値と最大値に対応しています。