注意到最终的序列一定是若干形如 $0,1,\cdots,k$ 的连续子序列拼接起来的，我们称这样的连续子序列为一个连续段。

为了方便优化，我们把问题变为至多保留多少个数的问题。设这个问题答案为 $a$，则原问题的答案为 $n-a$。

考虑 DP。设 $f_i$ 为将原数列 $[1,i]$ 区间调整为“好”的，且 $i$ 位置为一个连续段的末尾，至多保留多少数，$f_0$ 为 $0$。

显然有转移：

$$f_i=\max_{0 \le j < i}\{f_j + \sum_{k=j+1}^{i} [a_k=k-j-1]\}$$

这表示枚举 $j$，计算将 $[j,i]$ 作为一个连续段时的答案，时间复杂度 $O(n^3)$。
为了方便，令 $g_j=f_j + \sum\limits_{k=j+1}^{i} [a_k=k-j-1]$。转移方程为 $f_i=\max\limits_{0<j<i}\{g_j\}$。

考虑优化 $g_i$ 的计算，对于一个 $a_i$，通过上面式子发现他只会对 $g_{i-a_i-1}$ 产生 $1$ 的贡献。前提是 $i-a_i-1 \ge 0$。

这样有一个 $O(n^2)$ 的做法：在计算 $f_i$ 前，将 $g_{i-a_i-1}$ 加 $1$，计算 $f_i$，令 $g_i=f_i$。

用线段树可以优化到 $O(n \log n)$，但是没必要，也无法通过所有测试点。

注意到 $\max\limits_{0<j<i}\{g_j\}$ 在计算过程中是单调不降的，可以维护一个变量 $t=\max\limits_{0<j<i}\{g_j\}$。

具体为在将 $g_{i-a_i-1}$ 加 $1$ 后，令 $t=\max(t,g_{i-a_i-1})$。计算 $f_i,g_i$ 时令 $g_i=f_i=t$ 即可。

时间复杂度为 $O(n)$。代码难度几乎没有。

其实有一个另一个 $O(n^2)$ 的做法：设 $f_{i,j}$ 为考虑到 $a_i$，$a_i=j$ 时最多保留多少个数，对正解没有启发，故略去。

#include<bits/stdc++.h>
#define N 10010000
using namespace std;
int a[N],f[N],g[N],n,mx;
inline int read(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
	return x*f;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++){
		a[i]=i-a[i]-1;
		if(a[i]>=0) ++g[a[i]],mx=max(mx,g[a[i]]);
		g[i]=f[i]=mx;
	}
	return cout<<n-f[n],0;
}

---

另一个解法（By ）

设 $f_i$ 为 $a'_i = 0$ 时确定 $[i, n]$ 的最小代价，可以证明只有 $a_j = j - i$ 的转移点 $j$ 可能最优，变形得到 $a_j - j = -i$，由同一个 $j$ 可以唯一确定 $a_j - j$ 可知时间复杂度为 $O(n)$。