问题 J: 嘟嘟的搬砖机

问题 J: 嘟嘟的搬砖机

时间限制: 1 Sec  内存限制: 128 MB
提交: 442  解决: 194
[状态] [讨论版] [提交] [命题人:]
题目描述

嘟嘟是个勤奋的打工人,某一天,工头要求他在将一片废弃的砖堆垒成上升阶梯(只能加转,不能减砖),废弃的砖堆从侧面看可以看成是一条长度为 n 的数组X,而Xi就是砖堆在位置 i 处的高度,上升阶梯需要满足 Xi ≤ Xi+1 ( 1 ≤ i< n )。

嘟嘟准备了充足的砖块,但是搬砖机被工友们藏了起来,直接导致嘟嘟效率大减。  嘟嘟作为打工人就算是徒手搬砖也要完成工头的任务。 

已知嘟嘟徒手搬砖平均速度是一秒钟加一块砖头。即1秒钟可以选择任意一个数 i ( 1 ≤ i ≤ n ),使Xi+1

嘟嘟想尽快完成任务下班,请问嘟嘟最少需要多少秒钟才行完成任务?

输入

第一行输入一个整数n,代表废弃砖堆的长度。

第二行输入n个整数Xi代表废弃砖堆i处的原始高度。 (1 ≤ n ≤ 104, 0 ≤ Xi ≤104

输出
输出一个整数,代表嘟嘟完成任务下班需要的最短时间。
样例输入 Copy
6
1 4 3 4 3 6
样例输出 Copy
2
提示
样例解释:
在第一秒向位置3加一块砖,砖堆变成"1 4 4 4 3 6"
在第二秒向位置5加一块砖,砖堆变成“1 4 4 4 4 6”,满足阶梯条件完工。