014 - Frog1.5
時間制限 2 秒 / メモリ制限 128 MB / 得点 5 / x 3 /
問題
$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