You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

回想七尺风雪中归去

遥遥数月似无期

血染樱花烟云里

恰似无声的伏笔

万众一心烽烟起

若卒魂要归故里

思念明月落水底

儿女英雄为知己

题目描述

小t今天在玩一个塔防游戏，对面有 $n$ 座防御塔，他知道每一座防御塔的防守能力是多少。对于一座防守能力为 $x$ 的防御塔，需要 $x$ 发炮弹才能摧毁它。

为了不造成炮弹的浪费，每座防御塔只能接受 $x$ 枚炮弹，不能多也不能少。

小t在游戏中的大炮发射规则比较特别，每次可以选择一个区间 $[l,r]$，给这个区间的所有防御塔打出一枚炮弹。现在小t想要她的大炮发射次数最小，请问最少需要多少次发射？

输入格式

第一行一个数 $n$， 接下来一行 $n$ 个数，其中第 $i$ 个数表示第 $i$ 座防御塔的防守能力。

输出格式

一行一个数，为最小的大炮发射次数。

5
2 3 4 3 2

4

样例解释

选择的 $4$ 个区间分别为 $[1,5],[1,5],[2,4],[3,3]$。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,a_i \le 10^6$。