题目描述

徐老师非常开心的收回了整个西瓜地的西瓜，回家以后挑出了 $n$ 个最好的西瓜切好了摆成一排，准备请小伙伴们吃西瓜

但是有一丝丝强迫症的徐老师发现了一个问题

这 $n$ 个西瓜现在有大有小，排成一排以后非常难看

为了方便理解，徐老师决定用一个数字 $a_i$ 来描述第 $i$ 个西瓜的大小，数字越大西瓜越大

接下来他将要对一部分西瓜施展刚学来的西瓜魔法！

他的西瓜魔法是这样的，可以选择一段编号连续的西瓜施展魔法，一次性让这些西瓜的大小全部 $-1$

现在徐老师想知道，如果想要这 $n$ 个西瓜在不移动的情况下，使得从左到右的西瓜大小关系可以满足 $a_i <= a_j(i < j)$，至少需要使用几次西瓜魔法？

P.S. 有没有一个可能，西瓜魔法就是徐老师把每个西瓜吃掉一口呢？

输入格式

第一行一个整数 $n$,表示西瓜数量

第二行 $n$ 个整数表示每个西瓜的大小

输出格式

输出一行一个整数，表示答案。

Samples

3
1 3 2

1

数据范围

对于 $20\%$ 的数据，满足 $n,a_i\leq 10$。

对于 $40\%$ 的数据，满足 $n\leq 10^3$。

对于另外 $20\%$ 的数据，保证 $a$ 是一个不递增序列。

对于 $100\%$ 的数据，满足 $1\leq n\leq 10^6,1\leq a_i\leq 10^9$。