D - カーペット

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

• カーペットは研究室からはみ出してはいけない．
• カーペットはいくらでも重ねて敷くことが可能である．このとき，カーペットの厚さは無視する．
• カーペットを切り離して利用することはできない．
• カーペットは各辺がx軸またはy軸に平行になるように配置しなければならない．

研究室の床を覆い尽くすために必要なカーペットの最小数を求めよ．

図D-1. 入力例1の床

図D-2. 入力例2の床

入力形式

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

N
a_1 … a_N

出力形式

研究室の床を覆い尽くすために必要なカーペットの最小数を１行に出力せよ．

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq a_i \leq 10^9
• 入力値はすべて整数である．

入出力例

入力例1

3
1 2 1

出力例1

2

入力例2

10
1 2 2 1 3 4 3 1 2 2

出力例2

5