AtCoder Beginner Contest 040

C - 柱柱柱柱柱


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

N 本の木の柱が左から右へ一列に並んだアスレチックがあります。左から i 本目の柱の高さは a_i センチメートルです。

高橋君は左から 1 本目の柱からスタートし、右へ柱を渡っていき N 本目の柱まで行こうとしています。

高橋君がある柱にいるとき、次には現在の柱から 1 個もしくは 2 個右にある柱のどちらかへ移動することができます。

移動するときには、現在いる柱の高さと、移動後の柱の高さの差の絶対値のぶんだけコストがかかります。

N 本目の柱まで行くとき、コストの合計の最小値はいくらになるでしょうか。

制約

  • 2 ≦ N ≦ 100,000
  • 0 ≦ a_i ≦ 10,000
  • a_i はすべて整数である。

入力

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

N
a_1 a_2 ... a_N

出力

1 本目の柱から N 本目の柱へ移動するまでに必要な合計コストの最小値を 1 行に出力せよ。


入力例1

4
100 150 130 120

出力例1

40

このケースでは以下のような移動によって最小コストを達成できる。

  • 1 本目の柱から 3 本目の柱へ移動する。(コスト 30)
  • 3 本目の柱から 4 本目の柱へ移動する。(コスト 10)

合計コストは 40 となる。


入力例2

4
100 125 80 110

出力例2

40

このケースでは以下のような移動によって最小コストを達成できる。

  • 1 本目の柱から 2 本目の柱へ移動する。(コスト 25)
  • 2 本目の柱から 4 本目の柱へ移動する。(コスト 15)

合計コストは 40 となる。


入力例3

9
314 159 265 358 979 323 846 264 338

出力例3

310

Submit提出する