A - Frog 1

コンテスト時間: 2019-01-06(日) 11:00 ~ 2019-01-06(日) 16:00 (300分)

A - Frog 1 解説

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : $100$ 点

問題文

$N$ 個の足場があります。足場には $1, 2, \ldots, N$ と番号が振られています。各 $i$ ( $1 \leq i \leq N$ ) について、足場 $i$ の高さは $h_i$ です。

最初、足場 $1$ にカエルがいます。カエルは次の行動を何回か繰り返し、足場 $N$ まで辿り着こうとしています。

足場 $i$ にいるとき、足場 $i + 1$ または $i + 2$ へジャンプする。このとき、ジャンプ先の足場を $j$ とすると、コスト $|h_i - h_j|$ を支払う。

カエルが足場 $N$ に辿り着くまでに支払うコストの総和の最小値を求めてください。

制約

入力はすべて整数である。
$2 \leq N \leq 10^5$
$1 \leq h_i \leq 10^4$

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $h_1$   $h_2$   $\ldots$   $h_N$

出力

カエルが支払うコストの総和の最小値を出力せよ。

入力例 1Copy

Copy

4
10 30 40 20

出力例 1Copy

Copy

足場 $1$ → $2$ → $4$ と移動すると、コストの総和は $|10 - 30| + |30 - 20| = 30$ となります。

入力例 2Copy

Copy

2
10 10

出力例 2Copy

Copy

足場 $1$ → $2$ と移動すると、コストの総和は $|10 - 10| = 0$ となります。

入力例 3Copy

Copy

6
30 10 60 10 60 50

出力例 3Copy

Copy

足場 $1$ → $3$ → $5$ → $6$ と移動すると、コストの総和は $|30 - 60| + |60 - 60| + |60 - 50| = 40$ となります。

Score : $100$ points

Problem Statement

There are $N$ stones, numbered $1, 2, \ldots, N$ . For each $i$ ( $1 \leq i \leq N$ ), the height of Stone $i$ is $h_i$ .

There is a frog who is initially on Stone $1$ . He will repeat the following action some number of times to reach Stone $N$ :

If the frog is currently on Stone $i$ , jump to Stone $i + 1$ or Stone $i + 2$ . Here, a cost of $|h_i - h_j|$ is incurred, where $j$ is the stone to land on.

Find the minimum possible total cost incurred before the frog reaches Stone $N$ .

Constraints

All values in input are integers.
$2 \leq N \leq 10^5$
$1 \leq h_i \leq 10^4$

Input

Input is given from Standard Input in the following format:

 $N$ 
 $h_1$   $h_2$   $\ldots$   $h_N$

Output

Print the minimum possible total cost incurred.

Sample Input 1Copy

Copy

4
10 30 40 20

Sample Output 1Copy

Copy

If we follow the path $1$ → $2$ → $4$ , the total cost incurred would be $|10 - 30| + |30 - 20| = 30$ .

Sample Input 2Copy

Copy

2
10 10

Sample Output 2Copy

Copy

If we follow the path $1$ → $2$ , the total cost incurred would be $|10 - 10| = 0$ .

Sample Input 3Copy

Copy

6
30 10 60 10 60 50

Sample Output 3Copy

Copy

If we follow the path $1$ → $3$ → $5$ → $6$ , the total cost incurred would be $|30 - 60| + |60 - 60| + |60 - 50| = 40$ .