什么是“美”?在数学家眼中,秩序与不减的和谐即是最高级的“美”。面对一串杂乱无章的数字,你决定用最微小的代价,将其雕琢成一件完美的艺术品。
给定一个长度为 的正整数序列 。
一个序列被称为“美的”,当且仅当它是一个非严格递增的序列(即对于任意 ,都有 )。
每次操作,你可以选择序列中的任意一个元素,使其值 或者 。
请问,至少需要进行多少次操作,才能将给定的序列变成“美的”?(最终序列中的元素不必保持为正整数,可以为 或负数)。
第一行包含一个整数 ()。
第二行包含 个整数 ()。
输出一个整数,表示最少的操作次数。
【样例输入】
5 5 3 4 2 6
【样例输出】
4
【样例说明】
一种最优策略是将其变为序列 3 3 4 4 6(这满足非严格递增条件)。
3 3 4 4 6
代价计算: 次操作。
另一种也是最优的策略是变为 3 3 3 3 6,代价:。
3 3 3 3 6
最少需要 4 次操作。