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

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

Here is the solution with a lower complexity:

https://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.

Auto comment: topic has been updated by EErbium (previous revision, new revision, compare).Here is my solution easily understandable https://codeforces.com/contest/1917/submission/271166147