50041. Mountains

I'm a slow walker, but I never walk backwards.

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 $m_1, m_2, \cdots, m_n$ denote the mountains. The height of $m_i$ is denoted by $h_i$. We will start from $m_1$, then go $m_2$, then $m_3$, etc, and finally stop at $m_n$.

A transition describes how we get from one mountain to the next. There are two kinds of transitions when we go from $m_i$ to $m_{i+1}$. If $h_{i+1}$ is greater than $h_i$, 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 $m_4$ to $m_5$ is determined by itself and the type of the transition from $m_3$ to $m_4$. There are two cases:

  1. The cost of the first transition (from $m_1$ to $m_2$) 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 a downhill.
  2. 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 $h_1, h_2, h_3, h_4$ be $10, 20, 5$, and $3$.

  • The cost from $m_1$ to $m_2$ is $\vert 20-10\vert \times 3 = 30$ since it is the first transition and is an uphill.
  • The cost from $m_2$ to $m_3$ is $\vert 5-20\vert \times 3 = 45$ since it is a downhill and the previous transition ($m_1$ to $m_2$) is an uphill.
  • The cost from $m_3$ to $m_4$ is $\vert 3-5\vert \times 2 = 4$ since it is a downhill and the previous transition ($m_2$ to $m_3$) is also a downhill.

As a result, the total cost going from $m_1$ to $m_4$ is $30 + 45 + 4 = 79$.

Now given the heights of the mountains, please compute the cost going from mountain $m_1$ to mountain $m_n$.

Note that the memory limit is 1MB, so for some testcases with greater $n$, you cannot declare an array to store 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 Format

The input contains two lines. The first line contains an integer $n$, denoting the number of mountains. The second line contains $n$ integers, denoting $h_1, h_2, \cdots, h_n$.

Technical limitation

  • $2 \leq n \leq 1000000$
  • $1 \leq h_i \leq 500$

Output Format

Output the total cost going from $m_1$ to $m_n$.

Sample Input 1

4
10 20 5 3

Sample Output 1

79

Sample Input 2

4
30 5 20 50

Sample Output 2

215

Discussion