Hints : Chip and Ribbon

Solve for all permutation of [3, 4, 5] first.

Testcase:

6

3
3 4 5

3
3 5 4

3
4 3 5

3
4 5 3

3
5 3 4

3
5 4 3

If only teleport is allowed, then the total cost would be sum(a[i]). (We will subtract the 1 extra contribution for a[0] at the end).

Now, let’s introduce the first operation back. Notice that it helps you minimize the teleports of a[i], since it can now borrow some teleports from its left neighbor. Do we need to worry about whether the teleports of the neighbor were borrowed or original teleports?

If we have

a[i - 1] < a[i]
// Example (5, 8)

Then, no matter what happens, the chip starts at cell (i - 1) for exactly 5 times. We don’t care if it got to cell (i - 1) via sliding or teleport. All of these 5 instances would be help to help the a[i] element by carrying forward the teleportation. Hence, a[i] would only need to initiate a[i] - a[i - 1] = 8 - 5 teleports from its end. (Why not less? Because if the 6-th teleport were to slide from the a[i - 1] element, then it’s count would have to increase to 6).

Similary, if we had

a[i - 1] > a[i]
// Example (8, 5)

Then, a[i] doesn’t need to worry about its 5 teleports since all of those would be slided forwarded by a[i -1]. What happens to the remaining 8 - 5 = 3 teleports from a[i -1]? Their sliding stops at a[i - 1]^th element.

If teleports[i] represents the number of teleports needed to ensure that i element is covered correctly, then

teleports[i] = max(a[i] - a[i - 1], 0)
Answer = sum(teleports[i]) - 1