Platforms#2688
In classic video games, you might encounter a situation where a hero jumps across platforms suspended in the air, needing to move from one edge of the screen to the other. In one version of this game, when the hero jumps from one platform to a neighboring one, he uses |y_2 - y_1| energy, where y_1 and y_2 are the heights of these platforms. Additionally, there is a special move that allows the hero to skip a platform, costing 3 \cdot |y_3 - y_1| energy. Another version of the game differs only in that the cost functions use squares instead of absolute values: (y_2 - y_1)^2 for a jump to a neighboring platform and 3 \cdot (y_3 - y_1)^2 for skipping one. The heights of the platforms are given in sequence from the leftmost to the rightmost edge. For each version of the game, determine the minimum amount of energy needed to get from the st platform to the th platform.
The first line contains the number of platforms (2 \leq N \leq 50000), followed by integers, each between and , representing the heights of the platforms.
Output a single line with two space-separated integers—the minimum energy required for the first version and the second version of the game.
Example 1
In the first version, it is more efficient to jump consecutively across platforms 0 \to 20 \to 11, with a total expenditure of 20 + 9 = 29. In the second version, it is more efficient to jump directly from to (3 \cdot 11^2 = 363) than to jump across all platforms consecutively (20^2 + 9^2 = 481).