题目描述

小蓝正在设计一个排水管道的工程，将水从西边一个离地面很高的水库引到东边的地面。

为了项目更有艺术性，小蓝建造了很多高低不同的的柱子用于支撑流水的水槽，柱子之间的间距相同。

当西边的柱子比东边相邻的柱子至少高 $1$ 时，水能正常通过水槽向东流，否则可能出现异常。

但是，小蓝发现施工方建造的柱子是忽高忽低的，不满足西边高东边低的要求。小蓝不得不修改柱子的高度以便水能正常通过水槽。同时，小蓝需要用上所有的柱子，最东边的柱子高度至少为 $1$ ，最西边的柱子高度可以为任意高度。每修改一根柱子的高度，需要花费 $1$ 的代价（不管高度改变多少代价都是 $1$ ）。

请问，小蓝最少花费多大的代价，可以让水能正常通过所有水槽？在修改时，小蓝只会把柱子的高度修改为整数高度。

输入描述

输入的第一行包含一个整数 $n$ ，表示柱子的数量。

第二行包含 $n$ 个整数 $h_1,h_2,⋅⋅⋅,h_n$ ，从西向东表示每根柱子的高度。

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

6
8 9 5 2 1 1

至少修改三根柱子，高度变为 8,7,5,3,2,1。

对于 30% 的评测用例， $2≤n≤100，1≤h_i≤100$ 。

对于 60% 的评测用例， $2≤n≤1000，1≤h_i≤10000$ 。

对于所有评测用例， $2≤n≤100000，1≤h_i≤10^9$ 。