Pancake

Time Limit : 1 sec, Memory Limit : 262144 KB

パンケーキ

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

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

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

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

Input

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

N
p1 p2 ... pN

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

Output

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

Sample Input 1

3
1 2 1

Sample Output 1

4

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


Sample Input 2

3
0 3 0

Sample Output 2

6

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


Source: PC Koshien 2016 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2016-9-10
http://web-ext.u-aizu.ac.jp/pc-concours/