[COCI2020-2021#5] Po
题目描述
有一个长度为 $n$ 的数组。在初始状态下，所有元素都为 $0$。
每次操作，可以将一个连续的区间 $[l,r]$ 内的所有数加上一个正整数 $x$，但要求任意两个操作区间要么互不相交，要么一个包含另外一个。
请问能将原数组变为给定数组 $a$ 的最少操作次数。
输入输出格式
输入格式
第一行输入整数 $n$。
第二行输入 $n$ 个非负整数 $a_i$。
输出格式
输出所需最少操作次数。
输入输出样例
输入样例 #1
3
2 2 2输出样例 #1
1输入样例 #2
5
2 3 3 3 2输出样例 #2
2输入样例 #3
6
1 2 3 2 1 3输出样例 #3
4说明
#### 样例 2 解释
一种最优的方案是：将所有元素都加上 $2$，再将中间三个元素都加上 $1$。
#### 数据规模与约定
对于 $30$ 分的数据，$1 \le n \le 1000$。
对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le a_i \le 10^9$。
#### 说明
**本题分值按 COCI 原题设置，满分 $70$。**
**题目译自 [COCI2020-2021](https://hsin.hr/coci/) [CONTEST #5](https://hsin.hr/coci/contest5_tasks.pdf) _T2 Po_。**