I was trying to solve this problem for several days. I failed and read the editorial. But I couldn't understand the solution. Can someone please explain how they came up with that formula?

Thanks in advance :)