T5.粉刷栅栏 (brush)

• 时间限制：$1000ms$ ，空间限制：$512MB$

题目描述

春天来了，万物复苏，校园里的小农场也不例外。为了不辜负这美丽的春天，小潍和小阳打算粉刷农场的栅栏，他俩都有一把宽度为 $1$ 个单位的刷子。农场的栅栏共有 $n$ 块，宽度都是 $1$ 个单位 ，高度分别为 $h_1，h_2，...h_n$ 个单位 ，小潍喜欢竖着刷一块栅栏，小阳喜欢横着刷一段连续的栅栏，他们只能刷连续的一段，而且不能重复粉刷。他俩合起来粉刷完所有的栅栏最少需要多少次？

输入格式

共两行。 第一行一个整数，表示有 $n$ 个栅栏。 第二行 $n$ 个整数，第 $i$ 个数表示第 $i$ 个栅栏的高度。

输出格式

输出一行，包含 $1$ 个整数，表示小潍和小阳合起来需要的最少粉刷次数。

样例输入1

6
4 2 2 3 1 6

样例输出1

5

样例解释1

水平粉刷栅栏 $1-6$，水平粉刷栅栏 $1-4$ ，竖直粉刷栅栏 $1$、$4$ 和 $6$ ，共 $5$ 次。 $5$ 次的粉刷方式可能不唯一，但没有更少次数的粉刷方式。

样例输入2

8
7 3 4 6 5 8 6 3

样例输出2

8

样例解释2

每个栅栏竖着刷 $1$ 次，共 $8$ 次。

样例输入3

见下发文件brush\brush3.in

样例输出3

见下发文件brush\brush3.ans

数据规模与约定

对于前 $30\%$ 的数据，$1 \leq n \leq 100$，$1 \leq h_i \leq 100$ 。

对于 $100\%$ 的数据，$1 \leq n \leq 5000$，$1 \leq h_i \leq 10^9$。