
I also implementated <O(n), O(1)> algorithm and found that it works much slower than the <O(n*logn),O(1)> version. Maybe the input size we are looking at is smaller than what it should be so that <O(n),O(1)> algorithm runs faster. But in most contests <O(n*logn),O(1)> version should be quick and easy to implement. 