logo AlgoBeat OnlineJudge 返回比赛
登录 注册

D. [ABSEC0006] 美

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

什么是“美”?在数学家眼中,秩序与不减的和谐即是最高级的“美”。面对一串杂乱无章的数字,你决定用最微小的代价,将其雕琢成一件完美的艺术品。

给定一个长度为 的正整数序列

一个序列被称为“美的”,当且仅当它是一个非严格递增的序列(即对于任意 ,都有 )。

每次操作,你可以选择序列中的任意一个元素,使其值 或者

请问,至少需要进行多少次操作,才能将给定的序列变成“美的”?(最终序列中的元素不必保持为正整数,可以为 或负数)。

输入格式

第一行包含一个整数 ()。

第二行包含 个整数 ()。

输出格式

输出一个整数,表示最少的操作次数。

样例

【样例输入】

5
5 3 4 2 6

【样例输出】

4

【样例说明】

一种最优策略是将其变为序列 3 3 4 4 6(这满足非严格递增条件)。

代价计算: 次操作。

另一种也是最优的策略是变为 3 3 3 3 6,代价:

最少需要 4 次操作。