\begin{tutorial}{Паша також проти "хвостів"?}

\begin{center}
\begin{tabular}{rl}
\textbf{Автор задачі}: & \textbf{Павло Ціцей} \\
\textbf{Задачу підготували}: & \textbf{Павло ціцей, Олександр Тимкович} \\
\textbf{Розбір написав}: & \textbf{Павло Ціцей} 
\end{tabular} 
\end{center}

Рішення --- потрібно зводити кожен елемент до медіани масиву. Тобто якщо медіана це $x$, то відповідь це $\sum_{i=1}^n |a_i-x|$.

Доказ:

Будемо вважати що масив $a$ відсортований. Зафіксуємо якесь $k$ і доведемо що якщо зводити елементи масиву до $x+k$, то відповідь буде більша або рівна за правильну. За припущенням, правильна відповідь $\sum_{i=1}^n |a_i-x|$.

Через те, що $x$ --- це медіана, ми можемо це переписати як $$\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}x-a_i+\sum_{i=\lfloor\frac{n}{2}\rfloor+1}^{n}a_i-x$$Тепер запишемо відповідь для $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$$ де $y$ --- це індекс останнього елементу, що менше або рівне за $x+k$. Якщо $k>0$, то $y\ge\frac{n}{2}$ та віднявши 2 відповіді, ми отримаємо $$\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$$
Ми знаємо що $y\ge \frac{n}{2}$, тому $-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$, тому відповідь в цьому випадку більша або рівна. Для випадку коли $k<0$ рішення симетричне.


\end{tutorial}
