A61009.小明的非递减数组

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

给定一个长度为 nn 的数组 aa, 现在小明可以对数组进行操作, 每次操作可以选择一个数字 i(1in)i (1 \le i \le n) ,使得 aia_i11。请问最少经过几次操作可以使得数组变成一个非递减数组。

非递减数组 : 对于任意的数字 i(2in)i ( 2 \le i \le n) , 都满足 ai1aia_{i-1} \le a_i

输入格式

第一行给出一个整数 n(2n105)n (2 \le n \le 10 ^5) ;
第二行给出 nn 个整数, 代表数组 a(1ai109)a (1 \le a_i \le 10^9)

输出格式

输出一个整数,代表最少需要进行的操作次数。

输入输出样例

  • 输入#1

    5
    2 5 1 5 2

    输出#1

    7
首页