This was my solution with O(n^2) complexity which results in MLE:

https://mirror.codeforces.com/contest/1917/submission/238752759

Here is the solution with a lower complexity:

https://mirror.codeforces.com/contest/1917/submission/239038045

I did not understand what was done in the solution. Can anyone explain?

I read the editorial but can't understand that aswell.