粉刷栅栏

• 时间限制：1 秒
• 内存限制：512 MiB

题目描述

有 $n$ 块宽度均为 1、依次紧邻的竖直木板，第 $i$ 块高度为 $a_i$。你有一把宽度为 1 的刷子，每次可以进行一次竖直或水平描边；描边过程中刷子的整个表面都必须接触栅栏。已经刷过的区域可以重复粉刷。

求把整面栅栏完全粉刷所需的最少描边次数。

输入格式

第一行包含整数 $n$（$1\le n\le5000$）。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le10^9$）。

输出格式

输出一个整数，表示最少描边次数。

样例输入 1

5
2 2 1 2 1

样例输出 1

3

样例输入 2

2
2 2

样例输出 2

2

样例输入 3

1
5

样例输出 3

1

数据范围

对于所有数据，$1\le n\le5000$，$1\le a_i\le10^9$。