I wrote an O(n*log(n)) algorithm, but have got a TL.
I think this is a problem of Java language (there are arrays and garbage collector due to small memory limit).
And I saw that there is no AC on this problem using Java.
Can You change time-limit for Java on this task?

Edited by author 20.09.2007 15:54

If it's N*log(N) due to sorting, you can implement it at O(N) via bucket sorting. Bucketing array can be filled at O(N) along with list of non-empty buckets. Later this list can be used for O(N) sorted array traversal and for fast cleanup before further sorts.