My solution was $$$O(n\log^3 n)$$$ with some optimizations, I was trying to hack myself but I get a "Unexpected Verdict"(hack 678765).

Could you please have a look at this AliShahali1382?