linear time input + O(nlogn) time sorting + O(n)time availability checking gives ac in .015 sec and 150 kb.
I think better solution is possible. Please, let me know.