题目描述

给定一个长度为 $n(1 \le n \le 5000)$ 的数列 $a_1, a_2, \ldots, a_n(0 \le a_i \le 10^9)$。

你需要对这个数列进行若干次操作，操作分为如下两种类型：

• 操作1：任意选择一个区间 $[l, r]$（$1 \le l \le r \le n$），并将区间内的每个元素（即 $a_l, a_{l+1}, \ldots, a_r$）的数值均减去 $1$；
• 操作2：任意选择数列中的一个元素 $a_p(1 \le p \le n)$ 并将 $a_p$ 变小，但是 $a_p$ 最小只能变为 $0$。

求：最少需要执行几次操作能将数列中的所有元素都变为 $0$？

输入格式

第一行，一个整数 $n(1 \le n \le 5000)$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(0 \le a_i \le 10^9)$。

输出格式

输出一个整数，表示将数列元素都变为 $0$ 所需的最少操作次数。

样例输入1

4
1 4 1 1

样例输出1

2

样例输入2

5
1 0 1 0 1

样例输出2

3

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 50, a_i \le 1000$
• 对于 $60\%$ 的数据，$n \le 500, a_i \le 10^6$
• 对于 $100\%$ 的数据，$1 \le n \le 5000, 0 \le a_i \le 10^9$