I have two solutions.
The first easily gets AC, and the second passes stress test with the first but fails on the 12-th test.

If you know the 12-th test or some special cases for this problem, my email is sk1@hotbox.ru.

------------------
Sergey Kopeliovich