At first glance, the problem looks like a shortest-path or dynamic programming problem, since from every mark we may jump to many other marks. However, there is a much simpler way to look at the cost.

Consider the unit distance between marks ~i-1~ and ~i~. In any route from mark ~0~ to mark ~n~, this unit distance must be crossed from left to right at least once. If that crossing happens during a jump whose destination is mark ~j~, then necessarily ~j \geq i~, and that unit of distance contributes ~c_j~ to the cost of the jump.

Therefore, the contribution of this unit distance is at least:

$$\displaystyle \min(c_i, c_{i+1}, \ldots, c_n). $$

Backward jumps can only add extra positive cost, so they cannot improve this lower bound. Summing this argument over all unit distances gives:

$$\displaystyle \text{answer} \geq \sum_{i=1}^{n} \min(c_i, c_{i+1}, \ldots, c_n). $$

Now we show that this lower bound can always be achieved. Suppose we are planning to jump from mark ~a~ directly to mark ~b~, but there is some mark ~x~ between them with ~c_x < c_b~.

Jumping directly costs:

$$\displaystyle (b-a)c_b. $$

Going through ~x~ costs:

$$\displaystyle (x-a)c_x + (b-x)c_b. $$

Since ~c_x < c_b~, the second option is cheaper. So whenever we see a new smaller coefficient on the way to the destination, it is beneficial to land there first.

This means the optimal route uses exactly the marks that become suffix minimums. We do not need to construct the route explicitly. We scan the array from right to left, keep the minimum coefficient seen so far, and add it to the answer at every position.

For example, if:

$$\displaystyle c = [5,4,5], $$

then the suffix minimums are:

$$\displaystyle [4,4,5], $$

so the minimum total cost is:

$$\displaystyle 4+4+5=13. $$

Complexity

The array is scanned once from right to left, so the time complexity is:

$$\displaystyle O(n). $$

We store the array because the input is given from left to right and we process it backwards, so the memory complexity is:

$$\displaystyle O(n). $$

The answer can be as large as about ~10^{15}~, so a 64-bit integer type such as long long is required.