\begin{tutorial}{Pasha is also against "tails"?}

\begin{center}
\begin{tabular}{rl}
\textbf{Problem Author}: & \textbf{Pavlo Tsitsei} \\
\textbf{Prepared by}: & \textbf{Pavlo Tsitsei, Oleksandr Tymkovich} \\
\textbf{Tutorial by}: & \textbf{Pavlo Tsitsei} 
\end{tabular} 
\end{center}

Solution --- it is necessary to reduce each element to the median of the array. That is, if the median is $x$, then the answer is $\sum_{i=1}^n |a_i-x|$.

Proof:

Let's assume that the array $a$ is sorted. Let's fix some $k$ and prove that if we reduce the elements of the array to $x+k$, then the answer will be greater than or equal to the correct one. By assumption, the correct answer is $\sum_{i=1}^n |a_i-x|$.

Since $x$ is the median, we can rewrite it as $$\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}x-a_i+\sum_{i=\lfloor\frac{n}{2}\rfloor+1}^{n}a_i-x$$Now let's write the answer for $x+k$. $$\sum_{i=1}^n |a_i-x-k|=\sum_{i=1}^y x+k-a_i+\sum_{i=y+1}^n a_i-x-k$$ where $y$ is the index of the last element that is less than or equal to $x+k$. If $k>0$, then $y\ge\frac{n}{2}$ and subtracting 2 from the answers, we get $$\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}x-a_i+\sum_{i=\lfloor\frac{n}{2}\rfloor+1}^{n}a_i-x-\sum_{i=1}^y x+k-a_i-\sum_{i=y+1}^n a_i-x-k=$$
$$\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}x-a_i-x-k+a_i+\sum_{i=\lfloor\frac{n}{2}\rfloor+1}^y a_i-x-x-k-a_i+\sum_{i=y+1}^{n}a_i-x-a_i+x+k=$$
$$\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}-k+\sum_{i=\lfloor\frac{n}{2}\rfloor+1}^y -2\cdot x-k+\sum_{i=y+1}^{n}k=$$
$$-k\cdot\lfloor\frac{n}{2}\rfloor-2\cdot x\cdot (y-\lfloor\frac{n}{2}\rfloor)-k\cdot (y-\lfloor\frac{n}{2}\rfloor)+k\cdot(n-y)=-2\cdot x\cdot y+2\cdot x\cdot \lfloor\frac{n}{2}\rfloor-2\cdot k\cdot y+k\cdot n$$
We know that $y\ge \frac{n}{2}$, so $-2\cdot x\cdot y+2\cdot x\cdot \lfloor\frac{n}{2}\rfloor\le0$ and $-2\cdot k\cdot y+k\cdot n\le 0$, so the answer in this case is greater than or equal to. For the case when $k<0$, the solution is symmetric.

\end{tutorial}
