For people who will solve this problem in the future: it is possible to use floating point arithmetics and get AC with n^2*logn solution.