004 - FTBTｰtime attackｰ

問題

消防法で新しく、ビルの屋上にはかならずトランポリンをおかなければいけなくなった。というのも、ビルが火事になったときに屋上付近にいたときの避難は困難を極めるのでトランポリンをおいて火事になったときに隣のビルに飛び移って逃げるようにすれば被害をある程度押さえられると考えたからだ。
それから二十年と三年———。
ビルからビルをトランポリンを使って飛び移る(※1)エクストリームスポーツ、「(※2)FBTB」が老若男女問わず人気を博していた。

あなたはFBTBのタイムアタック選手だ。
FBTBの世界大会で勝つには当然、ビルからビルに飛び移るときの負担を最小にし、最短のルートを通らなければいけない。
だが、世界大会ともなるとビルは膨大な数用意され、それを飛ばなければいけない。となると、人力で最短ルートを求めるのはきわめて困難だ。そこでその最短のルートを求められるプログラムを作成することにした。
大前提としてFBTBのルールを学んでおこう。
・N本のビルが一列に並んだ通りがあり、スタートは必ず一本目のビルの頂上からとなる。
・ビルからビルを飛ぶ時は何本でも飛び越えてもよい。
以上の二つが基本ルールとなる。

しかし当然体力的な制約もあるわけで……
ビルの高低差によって飛び移る時のつらさが多くなる(現在いるビルの高さと移動後のビルの高さの差の絶対値がつらさとなる)。
また、あなたは長年の修練の成果もむなしく二本右にあるビルまでしか飛ぶことができない。

この条件の時にN本目の柱までいくときコスト(つらさ)の最小値はいくつになるか。

入力

N
a1 a2 a3 …　aN

制約

2≦N≦100,000
0≦a_i≦10,000
また与えられるビルの高さは必ず整数となっている。

出力

一本目からN本目のビルまでの最小コスト(つらさ)を一行に出力せよ。

入出力例

入力例1

4
100 150 130 120

出力例1

40

このケースでは以下の移動が最小コストを達成できる。
1本目から３本目のビルへ移動(130-100でコスト30)
3本目のビルから最後のビルへ(130-120でコスト10)
なので最小コストは40となる。

入力例2

4
100 125 80 110

出力例2

40

このケースでは以下の移動が最小コストを達成できる。
1本目から2本目のビルへ移動(125-100でコスト25)
2本目のビルから最後のビルへ(125-110でコスト15)
なので最小コストは40となる。

入力例3

9
314 159 265 358 979 323 846 264 338

出力例3

310

※1 エクストリームスポーツ　知らない人は調べてね
※2 FBTB 「From building to building」の略。出典:google翻訳