前后相加

给定一个序列，长度为 N，开始时，上面所有元素为 0。

你可以对序列作如下两种操作：

1.指定一个整数 k（1<=k<=N）和一个非降序列 c1,c2,c3,…,ck，（ci 非负， 1<=i<=k），对序列 x 的前 k 个数，令 xi=ci+xi。

2.指定一个整数 k（1<=k<=N）和一个非升序列 c1,c2,c3,…,ck，（ci 非负， 1<=i<=k），对序列 x 的后 k 个数，令 x[N-k+i]=ci+x[N-k+i]。

你的目标是将序列 x 构造为与序列 A 相等的序列，即 xi=Ai(1<=i<=n)，输出最少需要多少此操作，以达成目标。

数据范围

n<2e5

Ai<1e9

输入说明

第一行为一个整数 N，序列的长度。

第二行为 N 个整数，表示目标序列 A。

输出说明

输出最少的操作次数。

样例一

输入

5

1 2 1 2 1

输出

3

样例二

输入

5

2 1 2 1 2

输出

2