大样例下载

题目描述

hxy 想吃棒棒糖。

她正处于一个由一排共 $N$ 个巨大红西柚形成的区间里，初始时，她站在第一个红西柚上，而棒棒糖位于最后一个红西柚上。

hxy 需要从一个红西柚跳到相邻的下一个红西柚。

这些红西柚高度 $h_i$（均为整数）参差不齐，hxy 被难住了，因为一些原因，她获得了dzc的帮助。

dzc 从他的电子厂里调来了无限多个机器，消耗一个机器可以将一个红西柚的高度改为任意整数（当然，$1$ 号和 $N$ 号红西柚的高度也可变）。

hxy 是一个有上进心的人，所以她不想向下跳或者平着跳。

现在，请你帮助 hxy 和 dzc ，在能让 hxy 吃到棒棒糖的基础上，使得消耗机器尽量少。

输入格式

第一行，一个数 $N$，表示红西柚的数量。

第二行，$N$ 个数 $h_i$，表示第 $i$ 个红西柚的初始高度。

输出格式

一个数，表示最少消耗的机器数。

样例

5
0 0 3 1 3

3

数据范围

有20%的数据，满足 $3 \le N \le 10^3$
有100%的数据，满足 $3 \le N \le 10^6, 0\le h[i]\le 10^9$