14274: 【原4274】憨憨移书

题目

题目描述

author: wrz 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4274

问题描述

铁憨憨的桌上有n摞书，这n摞书从左到右排成一排，依次编号为1,2,...,n。其中第$i$摞书由$a_i$本书组成。

铁憨憨觉得这n摞书看起来不美观，因此它决定对它们进行调整，使得最后这n摞书所包含的书的数量严格单调增加。严格单调增加是指，经过调整后，对于任意相邻的两摞书，左边这一摞书的数量一定小于右边这一摞书的数量。

铁憨憨每一秒都可以选定这n摞书中的一些，对于被选中的每一摞书，铁憨憨既可以在这摞书的顶部加一本书，也可以从这摞书的顶部移走一本书。

需要注意的是，任一时刻都要保证每一摞书至少还有一本。因为如果一摞书被全部移走了，铁憨憨会不开心。

例如，如果铁憨憨有5摞书，这五摞书所包含的书的数量分别为：2,3,3,3,3。

铁憨憨花费1秒时间，从第1,2摞书的顶部移去一本，这五摞书变为1,2,3,3,3 铁憨憨再花费1秒时间，在第3,5摞书的顶部加上一本书，这五摞书变为1,2,4,3,4 铁憨憨再花费1秒时间，在第4摞书的顶部加上一本书，这五摞书变为1,2,4,4,4 铁憨憨再花费1秒时间，在第4,5摞书的顶部加上一本书，并且从第3摞书的顶部移走一本书，这五摞书变为1,2,3,5,5 铁憨憨再花费1秒时间，在第5摞书的顶部加上一本书，并且从第4摞书的顶部移走一本书这五摞书变为1,2,3,4,6

这样，铁憨憨花费了5s的时间将这5摞书变成了严格单调增加的。但实际上对于这5摞书，金憨憨发现只需要花2秒的时间就可以把它们调整成严格单调增加的，过程如下：

金憨憨花费1秒时间，从第2摞书的顶部移走一本，并在第5摞书的顶部加上一本书，这五摞书变为2,2,3,3,4 金憨憨花费1秒时间，从第1摞书的顶部移走一本，并在第4,,5摞书的顶部加上一本书，这五摞书变为1,2,3,4,5

这样，金憨憨比铁憨憨少花了3秒就完成了调整，这3秒就可以用来续给有需要的人。

铁憨憨自闭了，因此他需要你的帮助。铁憨憨希望你能算出最少需要几秒，才能把n摞书调整成严格单调增加的。

输入格式

第 1 行一个整数 $n$，表示有 $n$ 摞书。 第二行有 $n$ 个正整数，对于第i个整数$a_i$，表示第 $i$ 摞书由 $a_i$ 本书组成。

输出格式

输出一行一个整数，表示把这 $n$ 摞书调整成严格单调增加所需要的最少秒数。

样例输入

5 2 3 3 3 3

样例输出

2

样例解释

详见题面。

数据规模

对于所有的数据，$n\le 50,a_i\le 10^9$。

本题由10个测试点组成，通过每一个测试点得到10分。部分测试点的特性如下：

|测试点|特性| |----|----| |1|$a_i$严格单调增加| |2~4|$n$摞书的书本数量完全相等，也就是对于任意两摞书$i$和$j$，$a_i=a_j$| |5~6|$a_i$严格单调减少| |7~8|$a_i\le 3000$| |9~10|无特性|

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！