Zonal Computing Olympiad is round 1 out of 3 (i.e. beginner) for selection into Indian IOI team. Check out the discussion responses for solution one hint at a time!
I have implemented something similar to your stack solution and think it is O(n).I am not using sorting. Can you confirm-Solution: 25550837