Answer:$\frac{n^3-n}{3}.$ Example: $x_i=i$. Proof: Let $x_1<x_2<...<x_n$ which means $x_n \geq x_{n-1}+1 \geq ... \geq x_1+(n-1)$ There are no same number in the first column so the sum is $\sum{|x_i-x_j|}$ where $i,j \in 1,2,...,n$ $|x_1-x_1|+|x_1-x_2|+...+|x_1-x_n| \geq 0+1+...+(n-1)=\frac{(n-1)n}{2}$ $|x_2-x_1|+|x_2-x_2|+...+|x_2-x_n| \geq 1+0+1+...+(n-2)=\frac{(n-2)(n-1)}{2}+\frac{1.2}{2}$ $|x_3-x_1|+|x_3-x_2|+...+|x_3-x_n| \geq 2+1+0+1+...+(n-3)=\frac{(n-2)(n-1)}{2}+\frac{2.3}{2}$ $...$ $|x_n-x_1|+|x_n-x_2|+...+|x_n-x_n| \geq (n-1)+...+1=\frac{(n-1)n}{2}$ By adding these inequalities we get $\sum{|x_i-x_j|} \geq 2.(\frac{n(n-1)}{2}+\frac{(n-1)(n-2)}{2}+...+\frac{2.1}{2}+\frac{1.0}{2})=\frac{n^3-n}{3}$ which can be proved by induction.