Write a program to calculate the cost of fuel to go through a series of mountains.
We will go through a series of n mountains. Let m1, m2, … , mn denote the mountains. The height of mi is denoted by hi. We will start from m1, then go m2, then m3, etc, and finally stop at mn.
A transition describes how we get from one mountain to the next. There are two kinds of transitions when we go from mi to mi+1. If hi+1 is greater than hi, then this transition is an uphill. Otherwise, it is a downhill.
There is a cost associated with every transition. The cost of a transition is determined by the type of this transition and the one in front of it. For example, the cost of transition from m4 to m5 is determined by itself and the type of the transition from m3 to m4. There are two cases.
The cost of the first transition (from m1 to m2) is three times of the difference between the heights of this transition if it is an uphill, and twice the difference between the heights of this transition if it is an downhill.
The cost of other transitions is defined as follows:
When the transition is an uphill, then the cost is four times the difference between the heights of the current transition if the previous transition is an uphill, and three times the difference if the previous transition is a downhill.
When the transition is a downhill, then the cost is three times the difference
between the heights of the current transition if the previous transition is an uphill, and twice the difference if the previous transition is a downhill.
We illustrate the concept with an example of four mountains. Let h1, h2, h3, h4 be 10, 20, 5, and 3.
The cost from m1 to m2 is |20-10|*3 = 30 since it is the first transition and is an uphill.
The cost from m2 to m3 is |5-20|*3 = 45 since it is a downhill and the previous transition (m1 to m2) is an uphill.
The cost from m3 to m4 is |3-5|*2 = 4 since it is a downhill and the previous transition (m2 to m3) is also a downhill.
As a result, the total cost going from m1 to m4 is 30 + 45 + 4 = 79.
Now given the heights of the mountains, please compute the cost going from mountain m1 to mountain mn.
Note that the memory limit is 1MB, so you cannot declare an array to store the heights. As a result, you must remember the heights of the previous two mountains, so that you can calculate the cost when you read the next one.
Input
The input contains two lines. The first line contains an integer n, denoting the number of mountains. The second line contains n integers, denoting h1, h2, …, hn.
Task Description
Write a program to calculate the cost of fuel to go through a series of mountains.
We will go through a series of n mountains. Let m1, m2, … , mn denote the mountains. The height of mi is denoted by hi. We will start from m1, then go m2, then m3, etc, and finally stop at mn.
A transition describes how we get from one mountain to the next. There are two kinds of transitions when we go from mi to mi+1. If hi+1 is greater than hi, then this transition is an uphill. Otherwise, it is a downhill.
There is a cost associated with every transition. The cost of a transition is determined by the type of this transition and the one in front of it. For example, the cost of transition from m4 to m5 is determined by itself and the type of the transition from m3 to m4. There are two cases.
We illustrate the concept with an example of four mountains. Let h1, h2, h3, h4 be 10, 20, 5, and 3.
As a result, the total cost going from m1 to m4 is 30 + 45 + 4 = 79.
Now given the heights of the mountains, please compute the cost going from mountain m1 to mountain mn.
Note that the memory limit is 1MB, so you cannot declare an array to store the heights. As a result, you must remember the heights of the previous two mountains, so that you can calculate the cost when you read the next one.
Input
The input contains two lines. The first line contains an integer n, denoting the number of mountains. The second line contains n integers, denoting h1, h2, …, hn.
2 <= n <= 1000000 1 <= hi <= 500
Output
Output the total cost going from m1 to mn.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2