総合研究7号館の引越しに伴い,研究室にカーペットを敷くことになった. この問題では研究室を上から見たときの床を,二次元平面上の多角形とみなす. 床の形状を表す要素数Nの数列\{a_i\}が与えられる. R_iを,左下の座標が(i,0)で右上の座標が(i+1,a_i)である各辺がx軸またはy軸に平行な長方形の境界及び内部領域とする. このとき,床を表す多角形はR_1 ∪ R_2 ∪ R_3 ∪ … ∪ R_Nによって表される. カーペットは長方形であればどんな大きさのものを何枚でも用意することができる. 以下の条件を満たすようにカーペットを配置し,研究室の床を全て覆いつくしたい.
研究室の床を覆い尽くすために必要なカーペットの最小数を求めよ.
入力は以下の形式で与えられる.
N a_1 … a_N
研究室の床を覆い尽くすために必要なカーペットの最小数を1行に出力せよ.
3 1 2 1
2
10 1 2 2 1 3 4 3 1 2 2
5