I has written O(N^3) solution.
But I think there is O(N^2) one...
If somebody knows please tell me (here or sk1@hotbox.ru)