The editorial and other published solutions for this problem have at least O(n log n) time complexity. Here is a O(n) solution.

tl;dr for those who solved this problem with the Convex Hull Trick is that we can keep lines in a queue rather than a tree/sorted list, because we only add lines of increasing/decreasing slope. This solution doesn't require conceptualizing the geometry though .

The longer version

We have 2 cases: moving an item forwards or backwards. Since they are mirrors of each other, I'll only talk about the forwards case.

We iterate from 2->n and for each index we want to answer "which previously seen item is the best choice to move here?". We're going to build a queue where the first item of the queue is always the answer to this question. Why is this possible? Let's look at some examples:

[6,2,3,9,0,0,0] Input
[-,6,6,6,6,9,9] Best choice

To start, we put an item representing the 6 into our queue. As we pass through 2 and 3 we calculate the value for moving the 6 there, but we don't have to consider adding them to the queue. Intuitively, we want the small items to the left and the large items to the right. When we move from left to right and a new item is smaller than the largest item we've previously seen, it's always better to move the large item many steps rather than the small item fewer steps. This is the key insight.

After that we reach 9 and it's larger than 6, so we consider adding it to the queue. We want to know at what point it becomes better to move the 9 rather than the 6. Well, we know the value of moving the 6 onto the 9 = 6*3 — (9+2+3). We can consider this value as the "head start" that 6 has over 9. Then each additional step yields +6-t[i]. If we moved 9 instead of 6, each step would yield +9-t[i]. So each step further 9 "catches up" 6 by 3 points. This means we can formulate

Here is a commented java implementation (which runs in 200ms if we read input with a custom class). I struggled with my Convex Hull Trick implementation for a long time so it was pretty satisfying to find an alternate solution with better time complexity. Thanks to zscefn, pllk, Laakeri and OliKoJo for helping me debug & helpin me understand the geometry behind this.