Most people implemented a O(n) solution, but I did not understand their logic :(

There are few successful solutions in Python like: http://mirror.codeforces.com/contest/877/submission/31636672 They have used different approach

On other platforms like Codechef, for Python time is 5x of C/C++ Anyway, I see a lot of solution with single loop, but cannot understand the logic :(

Could someone please explain how B can be solved in Linear time? I get Time Limit exceeded for the editorial solution which is O(n^2)

Could you provide the formula? Brute force soln in tutorial is n^2 and gets Timed out.