i use O(nlogn) and got AC, if you use O(N) for this problem, plz tell your algo to me.

sorry for my poor english.