006 - パンケーキの焼き上がり

問題

あなたが勤めているパンケーキ屋では、細長い鉄板にパンケーキの生地を横１列に並べて焼きます。パンケーキはへらで何回か裏返せば完成します。何回以上裏返せば完成するかはパンケーキごとに異なります。

へらは大きいので、隣り合ったパンケーキは２枚同時に裏返されてしまいます。このとき、これら２枚の位置は入れ替わりません。ただし、両端だけは、隣のパンケーキといっしょに裏返すだけでなく、１枚だけ裏返すこともできます。すべてのパンケーキを必要な回数以上裏返したら、全部いっぺんに鉄板からおろして完成です。

パンケーキを必要な回数より多く裏返すと固くなってしまうので、あまり多く裏返したくありません。そこであなたは、すべて完成するまでに、各パンケーキが裏返る回数の総和が最小になるような方法を見つけようと考えました。

課題

鉄板の上のパンケーキの枚数と、完成するまでに何回以上裏返さなければならないかがパンケーキごとに与えられているとき、すべて完成するまでに各パンケーキが裏返る回数（へらを操作する回数ではない）の総和の最小値を計算するプログラムを作成せよ。

入力

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

N
p1 p2 ... pN

１行目にパンケーキの枚数 N(3≦N≦5000)が与えられる。２行目に各パンケーキが完成するまでに必要な裏返す回数 p_i(0≦p_i≦3)が与えられる。

出力

すべて完成するまでに各パンケーキが裏返る回数の総和の最小値を１行に出力する。

---

入出力例

入力例1

3
1 2 1

出力例1

4

解説

へらを１回操作して左端と真ん中のパンケーキを裏返すと、２個のパンケーキが１回ずつ裏返るので、この操作で裏返る回数は２回。さらに、へらを１回操作して真ん中と右端のパンケーキを裏返すと、２個のパンケーキが１回ずつ裏返るので、この操作で裏返る回数は２回。以上の総和４回が答えになる。

入力例2

3
0 3 0

出力例2

6

解説

へらを１回操作して左端と真ん中のパンケーキを裏返すと、この操作で裏返る回数は２回。これを３回繰り返したときの、総和の６回が答えになる（真ん中のパンケーキは、両隣のどちらかのパンケーキと一緒に裏返すことしかできないことに注意）。