1820 - Frog1.5

時間制限 2 秒 / メモリ制限 128 MB / 得点 10000 / Writer ei2326 / x 4 / 統計 /


TLE
2sec
MLE
128MB
得点
10000

問題

$N$個の足場があります。足場には$1,2,...,N$と番号が振られています。各$i(1 \leq i \leq N)$について、足場$i$の高さは$h_i$です。
最初、足場$1$にカエルがいます。カエルは次の行動を何回か繰り返し、足場$N$まで辿り着こうとしています。
・足場$i$にいるとき、足場$i+1$または$i+2$へジャンプする。このとき、ジャンプ先の足場を$j$とすると、コスト$|h_i - h_j|$を支払う。
また、カエルは最大で一度だけ次の行動が出来ます。
・足場$i$にいるとき、足場$i+3$へジャンプする。このとき、ジャンプ先の足場を$j$とすると、コスト$|h_i - h_j|$を支払う。
カエルが足場$N$に辿り着くまでに支払うコストの総和の最小値を求めてください。

入力

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

$N$
$h_1$ $h_2$ ... $h_N$

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

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

入出力例

入力例1

5
1 2 9 9 1

出力例1

2

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

入力例2

7
1 4 6 5 2 7 8

出力例2

7

入力例3

8
10 120 140 110 90 30 70 20

出力例3

190

入力例4

15
831 605 44 451 185 649 661 961 258 649 21 958 75 898 479

出力例4

1390