The solution involves trying every possible prefix of the sequence and checking its cost. To make a sequence with the minimal cost, you can add ~-1, -2, \dots, -2, -1~ to the sequence to reduce it to the problem of making all the elements in a sequence the same. This is a classical problem where you just change all the elements to the median (proof is left as an exercise for the reader). This algorithm is ~\mathcal{O}(N^2)~, but you can use data structures such as a segment tree to speed it up to ~\mathcal{O}(N \log^2 N)~.

Time complexity: ~\mathcal{O}(N \log^2 N)~