Computer Game (Platforms)
Can you think of any acquaintance under the age of twenty who didn't play computer games as a child? If so, perhaps you're not familiar with this pastime yourself. However, this shouldn't pose any difficulty in solving this problem.
In many classic games with two-dimensional graphics, you might encounter a scenario like this: a hero jumps across platforms (or islands) suspended in the air, trying to make his way from one side of the screen to the other. When the hero jumps from one platform to an adjacent one, he uses (|y_2-y_1|) energy, where (y_2) and (y_1) are the heights of these platforms. Additionally, the hero has a special move that allows him to jump over a platform, but this costs (3 |y_2-y_1|) units of energy. Naturally, energy must be conserved as much as possible.
Given the coordinates of all platforms in order from the left edge to the right, can you determine the minimum amount of energy the hero needs to travel from the first platform to the last?
Input
The first line contains the number of platforms (n) ((1 n 30000)). The second line contains (n) natural numbers, each not exceeding 30000, representing the heights of the platforms.
Output
Output a single number: the minimum amount of energy the player must expend to traverse the platforms (assuming that cheat codes cannot be used).