Link to the problem: click here

Summary. Given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. In one operation, we can move one unit from $$$a_i$$$ to an adjacent position. We need to find the minimum number of operations such that $$$a_i \geq b_i$$$ for all $$$i$$$. It is guaranteed that a solution always exists.

Constraints. $$$n \leq 5\cdot 10^5; a_i, b_i \leq 10^6$$$.

I have already come up an approach for the subtasks with $$$\sum_{i = 1}^n a_i = \sum_{i = 1}^n b_i$$$, when the target become to make $$$a_i = b_i$$$ for all $$$i$$$.

Let $$$pref_i = \sum_{i = 1}^n (a_i - b_i)$$$. If $$$pref_i \gt 0$$$, it means that the left side has $$$pref_i$$$ extra units, so we have to move them to the right side. Otherwise, the left side is missing of units, so we have to move $$$-pref_i$$$ units from the right side to the left side. In both cases, exactly $$$|pref_i|$$$ units will cross the gap between positions $$$i$$$ and $$$i + 1$$$. This implies that the answer will be $$$\sum_{i = 1}^n |pref_i|$$$.

However, I am stuck on how to generalize this to the full problem and also could not understand the accepted submissions. Any hints or explanations would be appreciated. Thanks!