First I did a $$$O(n^2)$$$ dp then optimised it to $$$O(n)$$$ For $$$O(n^2)$$$ I did a naive dp with dp[i][done] telling if we have done the range operation or not till i. So transitions are just

This a very naive dp. To optimise the top term we can see that we can use prefix sum. So we just store the

And to optimise the bottom term we can multiply the

and get the common j terms out. So

So

So now dp transition will be like

and

and this is

:yayy: