I was trying to solve this problem, after submitting my solution I got TLE and I couldn't figure out the problem with my O(n.log(n)) solution, I also checked some accepted solution and most of them are using the same approach?
UPD
I got accepted by copying someone sort function but I still want to know what's wrong with java.util.Arrays.sort function?
probably because of sorting long integer array in Java, there was a post yesterday or a day before that about the same issue.
I don't think so if you check my submissions, I used int array but also got TLE.
I have discussed about this already in this blog
Here is your AC code (Just shuffle the array before sorting)
Thank's a lot, btw I also got AC by changing variables types to reference data types (long -> Long).