Finding a permutation $p$ of $x_1, x_2, \dots, x_n$ which maximises $\sum_{i=1}^{n-1}|x_{p_{i+1}}-x_{p_i}|$ Here is the algorithmic problem I'm trying to solve:

Given a list of integers $x_1, x_2, \dots, x_n$ find a permutation $p_1, p_2, \dots, p_n \in [n]$ that maximises the sum $\sum_{i=1}^{n-1}|x_{p_{i+1}} - x_{p_i}|$.

I think this can be solved in $O(n\log n)$, I thought of sorting the list and returning a list where first element is maximum element, next element is minimum, next is maximum of those which are left, etc. But this leads to nowhere, I cannot prove that it's correct, so probably it isn't. So, any tips how to tackle this problem?
I found that the problem has been used in a student programming contest.

... if you still want to try to solve it by yourself don't move the mouse over the area below !!! :-)


  The programmingn contest is the Bubble Cup 7DC, Belgrade 2012.The key idea to solve it is to consider the middle element of the given array after sorting it in increasing order (if the number of elements is even then pick the value between the two middle elements); it splits the set in two halves $A$ and $B$.Then it is easy to prove that an optimal solution cannot contain three consecutive elements in increasing (or decreasing) order $... x_i &lt; x_j &lt; x_k ...$ because it is enough to move the middle element at the end of the array and the sum cannot decrease after the trasformation. So an optimal solution must proceed in a zig-zag style. Then we can prove that the optimal solution cannot contain two consecutive elements from the same side. Suppose that we have somewhere $... x_i, x_j, x_k ...$ with $x_i&gt; x_j &lt; x_k$ and $x_i, x_j, x_k \in B$. Then then the remaining sequence must contain three consecutive elements from $A$  $...x'_i,x'_j,x'_k...$ ordered as $x'_i &lt; x'_j &gt; x'_k$. Then $A \ni x'_j &lt; x_j \in B$ can be swapped preserving the inequalities and strictly increasing the value of the sum.For the detailed proof see: Bubble Cup 7DC - Problem C: MaxDiff(it contains other nice problems)