题目描述

你现在处于一个棋盘当中，长度为$n,$高度无限，棋盘上的每一列 有蓝色格子 和 白色格子组成，例如下图所示，我们现在要求将所有的格子都染成蓝色，每次染色你有两种方案：

1. 选择指定区间的列，将这段区间内的一行染成蓝色，注意，已经是蓝色的格子，不能重复再染；

2. 选择某一列，染成蓝色；

问你最少需要染色多少次？

输入格式

输入共两行;

第一行一个整数$n$，表示总共有多少列；$1 \le n \le 10^4$;

第$2$行$n$个数字，表示棋盘当中每一列下方的白色的格子的数目；

第$i$个数字$a_i$表示第$i$列的白色格子的数目，$0 \le a_i \le 10^4$

输出格式

一行一个数字，表示最少染色次数；

样例

5
2 1 2 2 1

3

数据范围与限制

• 对于$30\%$,$n \le 20,a_i \le 10000$
• 对于另外$20\%$的数据，$n \le 10000,a_i \lt a_{i + 1}$;
• 对于另外$20\%$的数据，$n \le 10000$,$\forall i \in [1,n],a_i = a_{i + 1}$;
• 对于$100 \%$的数据，$n \le 10^4,0 \le a_i \le 10000$

提示

样例1解释

如上图所示，总共有$5$列， 第一列有两个白色格子，第$2$列有$1$个，第$3$列有$2$个，第$4$列$2$个，第$5$列$1$个；

那么总共需要染色的次数 最少为$3$次;

• 第$1$次，将第$1$列到第$5$列的第一行全部染成蓝色，此时数组的状态为$[1,0,1,1,0]$;

• 第$2$次将第$1$列染成蓝色，此时数组的状态为$[0,0,1,1,0]$;

• 第$3$次将第$3$列到第$4$列总共染成蓝色；

此时数组的状态为$[0,0,0,0,0]$，每一列都没有白色格子，所有的都变成了蓝色，染色完毕；