WLOG let $x_1\leq x_2\leq\dots\leq x_n$. Its easy to see that in this sum, $x_n$ appears positively $2(n-1)$ times, and never appears negatively. $x_{n-1}$ appears positively $2(n-2)$ times, and appears negatively twice, so its coefficient is $2(n-3)$. Following this pattern, the sum in question is $2(n-1)x_n+2(n-3)x_{n-1}+\dots-2(n-1)x_1=2(n-1)(x_n-x_1)+2(n-3)(x_{n-1}-x_2)+\dots\leq 4(n-1)+4(n-3)+\dots$. If $n=2k+1$, the sum is $4(2k)+4(2k-2)+\dots+4(2)=8(k+(k-1)+\dots+1)=4k(k+1)=4k^2+4k<4k^2+4k+1=n^2$, and if $n=2k$, the sum is $4(2k-1)+4(2k-3)+\dots+4(1)=4(k^2)=n^2$, and we are done. Equality is only achieved when $n=2k$ and $x_1=x_2=\dots=x_k=0$ and $x_{k+1}=x_{k+2}=\dots=x_n=2$