この問題はシミュレーションによる考察を問います。

$O(W\log_{}W)$ 解法 (TLE)

それぞれの要素に操作を行った後、$M-m$ を最小化させる問題は、「要素を小さい順に操作をしていく」ことが典型です。
この問題の場合、一番大きい要素は変更することは最適ではありません。なぜかというと、$M-m$ の式から明らかに増加していってしまうためです。

なので $M$ は与えられた際の数列の中で一番大きい要素、すなわち $M=\max(A_i)$ とします。
そして $M$ を基準に $m=\min(A_i)$ を増加させていきます(すなわちできるだけ $M$ を除くすべての要素に対して $M$ に近づけたい)。

$A$ に直接操作を施すので $A$ は操作の順番に応じて変化します。しかしなるべく小さい要素から更新していきたいです。
これを実現させるためには、優先度付きキューを用いて実装することが適切です。

このキュー( $Q$ とします)を用いることで、より $M$ に近づけることができます。
具体的には $Q$ から $2$ 番目に大きい※要素 $b_2$ を取り出し、$M\ne b_2$ ならば $b_2$ を $1$ ずつ増加させます。
逆に $M=b_2$ ならば $M-m=M-b_2=M-\min(Q_i)=0$ を満たしていることが分かるので操作を終えます。

ただし $M$ は操作させないようにするため、$Q$ から $M=\max(A_i)$ は除外して考えることに注意する必要があります。
以上からこの方針で実装すると $O(W\log_{}W)$ となります。

...しかし制約上 $W\le 10^9$ であるため、時間制限には間に合いません。では、どうしたらよいでしょうか？

※$M=\max(A_i)$ を除外しているので、これは単に $Q$ から一番小さい要素を取り出すことと同値です。

$O(N\log_{}N+\max(A_i))$ 解法

上で書いた $O(W\log_{}W)$ 解法を用いて、実際に要素を更新する手続きを書き表してみます。例えば $A=(3,4,1,3,2),W=6$ としてみます。
$Q$ は $A$ を昇順に並び替えるため、最初 $Q=(1,2,3,3)$ となります($Q$ から $M=\max(A_i)=A_2=4$ は除外することに注意してください)。
また常時 $Q$ は昇順に並べ替えられることに注意してください。

• $b_2=Q_1=1$ である。$4\ne 1$ であるから、$b_2$ を $1$ 増やして並び替えると $Q=(2,2,3,3)$ となる。($W=5$)
• $b_2=Q_2=2$ である。$4\ne 2$ であるから、$b_2$ を $1$ 増やして並び替えると $Q=(2,3,3,3)$ となる。($W=4$)
• $b_2=Q_1=2$ である。$4\ne 2$ であるから、$b_2$ を $1$ 増やして並び替えると $Q=(3,3,3,3)$ となる。($W=3$)
• $b_2=Q_1=3$ である。$4\ne 3$ であるから、$b_2$ を $1$ 増やして並び替えると $Q=(3,3,3,4)$ となる。($W=2$)
• $b_2=Q_1=3$ である。$4\ne 3$ であるから、$b_2$ を $1$ 増やして並び替えると $Q=(3,3,4,4)$ となる。($W=1$)
• $b_2=Q_1=3$ である。$4\ne 3$ であるから、$b_2$ を $1$ 増やして並び替えると $Q=(3,4,4,4)$ となる。($W=0$)

こうして $Q$ の変化をよく見てみると、次のことが分かります。

• $A$ を昇順に並べ替えた数列 $A'=(A_1',A_2',\dots ,A_N')$ とします。また連続する整数の集合を $S$ として $A'=(S_1,S_2,\dots ,S_n)$ と表すことにする。
  ここで $n$ は $A$ に含まれる整数の個数と一致する。
  このとき $k=1,2,\dots ,N-1$ に対して $S_k\ne S_{k+1}$ である限り $S_k$ に含まれる一番小さい要素を $1$ ずつ足していくことが最適である

ここで集合 $X,Y$ が $X=Y$ を満たすとは、$X$ と $Y$ いずれも集合の要素数を問わず、要素がすべて同じであることと定義します。
反対に $X\ne Y$ を満たすとは、 少なくとも一方が $X,Y$ で異なる要素を含むことと定義します。

例えば $X=(2,2,2),Y=(2,2)$ や $X=(1),Y=(1,1)$ などは $X=Y$ であり、$X=(2,2,3),Y=(2,2)$ や $X=(2,2,2),Y=(2,1)$ などは $X\ne Y$ です。

したがって本問題は最初に与えられる数列 $A$ に含まれる整数に依存する問題に帰着することができました。
具体的には、次のような手続きを行えばよいです。ここで便宜上、現時点 $Q$ に含まれる任意の整数 $k$ の個数を $\text{cnt}(k)$ と表します。

• TLEになる上に書いた解法と同じ通り、$M$ を除外して考えるので $i=2,3,\dots ,N$ に対して $\text{cnt}(A_i')$ を数える
• その後 $x=1,2,\dots ,\max(A_i)(=A_N')$ に対して以下を $W$ が $0$ 以下になるまで繰り返す
  • $\text{cnt}(x)=0$ なら考えないので、$x$ を $x+1$ に更新してからそのあとの処理を飛ばす
  • $\text{cnt}(x+1)$ に $\min(W,\text{cnt}(x))$ だけ加算し、それぞれ $W,\text{cnt}(x)$ から $\min(W,\text{cnt}(x))$ だけ減少させる
  • $x$ を $x+1$ に更新して、上の操作を繰り返す

この計算を終えた後、$v=1,2,\dots ,\max(A_i)=A_N'$ の順で、初めて $\text{cnt}(v)\gt 0$ を満たす $v$ が、最終的に求める $m$ になります。
よってこの解法で求める答えは $M-m=A_N'-v$ となります。

$A$ をソートするのに $O(N\log_{}N)$ を要することに注意して、以上からこの解法では計算量が $O(N\log_{}N+\max(A_i))$ となります。$A_i\le 10^5$ という制約から、この問題を解くことができました。