Think about O(N) solution, task much easier than is looks like.

I use queue and got AC despite my solution probably has O(N * queue_work_complexity), not clearly O(N)