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.