I was solving this problem.
it kept on giving me TLE. Then i realized i need to learn Divide and conquer optimization. Now I don’t know how to apply DC optimization in this problem. Moreover is there any link from where i can learn. Most of the blog actually 3 found were very confusing.