由于综合研究7号楼搬迁,我们决定在研究室安装地毯。 在这个问题中,从上方看实验室的地板被视为二维平面上的多边形。 代表地板形状的元素数量N序列 使用\{a_i\}。 R_i,左下坐标为 右上角坐标为(i,0)设(i+1,a_i)为边平行于 x 轴或 y 轴的矩形的边界和内部区域。 在这种情况下,代表地板的多边形是 由R_1 ∪ R_2 ∪ R_3 ∪ … ∪ R_N代表。 您可以准备任意数量、任意尺寸的地毯,只要它们是矩形的即可。 我想布置地毯,使其满足以下条件并完全覆盖实验室的整个地板。
- 地毯不得超出实验室范围。
- 地毯可以按照您喜欢的层数铺设。这时,地毯的厚度就被忽略了。
- 地毯不能分开使用。
- 放置地毯时必须确保其每一侧均平行于 x 或 y 轴。
【原图片从这里到原衣容器传送:输入示例1楼】
图 D-1。输入示例 1 中的楼层
【原图片从这里到原衣容器传送:输入示例2楼】
图 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