Hello codeforces, I solved This problem from atcoder with the "Obvious" **brute-force** solution which is O(N). But when I take a look at the editorial I found a **Beautiful** mathematical solution that solves it in ~~O(1)~~ O(N) but with a lower constant factor, use lower memory and easy beautiful code. But unfortunately, I didn't understand it so Can anyone please explain it to me?

I really appreciate any help you can provide.