How to solve CM_CAN(Cman and Candies)?

How to solve this problem: CN_CAN problem, we need to find absolute difference sum of an array, i know we can do this by sorting whole array, like this. But here we need to print the whole array also ie cant sort/rearrange the array, how to do this in time limit ie in better than n^2?