問題文の「値が \(k\) 以上 \(k+1\) 未満」の部分を「値が \(k\) 以上 \(k+1\) 以下」と変更すると、求めるものは中央値と平均値の差の絶対値の最小値になります。

ありえる下限の値からなる昇順の列を\(x_i\) とします。
すなわち、例えば入力例 2 の場合 \((x_1,x_2,x_3,x_4)=(0,0,1,4)\) とします。このときの平均値を \(\mu\)、中央値 \(m\) とします。ここから少しずつ各 \(x_i\) の値を大きくすることをを考えます。

必要なら全ての \(x_i\) を \(-x_{N+1-i}-1\) に置き換えてることで \(\mu\leq m\) としてよいです。なぜならこの置き換えでは以下が全て成り立つためです。

• 中央値と平均値の差の絶対値が保たれる(求める答えが変化しない)
• \(x_i\) が昇順である状態が保たれる
• 各 \(x_i\) はその値が取りうる最小値を取っている状態が保たれる(すなわち \(x_i\) を\(x_i\) 以上 \(x_i+1\) 以下の任意の値に変更できる)

この状態から始めて、中央値を変化させないようにしたまま各値を大きくします。中央値を変化させないためには

• \(N\) が奇数のとき、\(x_i=m\) であるような \(i\leq \frac{N}{2}\)
• \(N\) が偶数のとき、\(x_i=x_\frac{N}{2}\) であるような \(i\leq \frac{N}{2}\) と、\(i=\frac{N}{2}+1\)

の \(x_i\) の値は変化させることができません。逆に、これら以外値は自由に変化させることができます。平均値を大きくすることが目的なので、変化させることができる値を全て上限に置き換えたときの平均値を \(\mu'\) とします。

この値の変化を連続的に行うことを考えると、\(x_i\) の平均値は \(\mu\) から \(\mu'\) の間の値を自由に取ることができるとわかります。よって、もし \(\mu'\geq m\) であれば答えは \(0\) です。

\(\mu'< m\) のケースを考えます。このとき仮定から、中央値の値を変化させることなく平均値を大きくすることはできません。しかし、中央値を \(\epsilon\) 大きくさせても、平均値は高々 \(\epsilon\) しか大きくできません。（前述の操作で変化させることができなかった値の個数を \(k\) として、中央値を \(\epsilon\) 大きくさせても、合計は高々 \(k\epsilon\) しか大きくならないため、平均は \(k\epsilon/N < \epsilon\) しか大きくなりません）

よってこれ以上平均値と中央値の差を縮めることはできず、\(m-\mu'\) が答えになります。

以上をまとめると \(\max(0,m-\mu')\) が答えです。これまでに述べた操作を全て具体的に \(x_i\) を使って行うことで、(入力の読み込みを除き)\(O(N)\)で答えを求めることができます。