题目描述

有一个长度为 $n$ 的数组。在初始状态下，所有元素都为 $0$。

每次操作，可以将一个连续的区间 $[l,r]$ 内的所有数加上一个正整数 $x$，但要求任意两个操作区间要么互不相交，要么一个包含另外一个。

请问能将原数组变为给定数组 $a$ 的最少操作次数。

输入格式

第一行输入整数 $n$。

第二行输入 $n$ 个非负整数 $a_i$。

输出格式

输出所需最少操作次数。

3
2 2 2

1

5
2 3 3 3 2

2

6
1 2 3 2 1 3

4

提示

样例 2 解释

一种最优的方案是：将所有元素都加上 $2$，再将中间三个元素都加上 $1$。

数据规模与约定

对于 $30$ 分的数据，$1 \le n \le 1000$。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le a_i \le 10^9$。

说明

本题分值按 COCI 原题设置，满分 $70$。

题目译自 COCI2020-2021 CONTEST #5 T2 Po。