luogu#P3902. 递增

    ID: 7930 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>动态规划dp树状数组离散化二分查找

递增

题目描述

现有数 A1,A2,,AnA_1,A_2,\cdots,A_n,修改最少的数字为实数,使得数列严格单调递增。

注:原题误表述为修改为整数,现已纠正为实数。本题数据确保按照修改为整数的做法也可以 AC(只是不能过样例)

输入格式

第一行,一个整数 nn

第二行,nn 个整数A1,A2,,AnA_1,A_2,\cdots,A_n

输出格式

1 个整数,表示最少修改多少个数字

3
1 3 2
1
8
1 2 3 4 4 5 6 7
1

提示

• 对于50% 的数据,N103N \le 10^3

• 对于100% 的数据,1N105,1Ai1091 \le N \le 10^5 , 1 \le A_i \le 10^9