给定一个长度为$n$数列$\{a_n\}$，你可以进行如下操作：

• 任意选择一个区间$[l,r](l\le r)$，使区间内的每一个数减$1$；
• 任意选择一个点$p$和一个正整数$x(x\ge 1)$，使$a_p$减去$x$。

求把原数列全部变为$0$的最少的操作次数。 $1\le n\le 5000$，$0\le a_i\le 10^9$。

输入格式

第一行给一个整数 $n$ ( $1 \le n \le 5000$ ) 表示数列长度

接下里$n$个整数 $a_1$ , $a_2$ , ..., $a_n$ ( $0 \le a_i \le 10^9$ ).

输出格式

输出一个整数，代表最少的操作次数

样例 #1

样例输入 #1

4
1 4 1 1

样例输出 #1

2

样例 #2

样例输入 #2

5
1 0 1 0 1

样例输出 #2

3