题意：数列A1,A2,...,AN，修改最少的数字，使得数列严格单调递增。(1<=N<=10^5; 1<=Ai<=10^9 )
思路：首先要明白的一点是数列是严格单调递增，那么没有修改的最长上升子序列也是严格单调递增的，并且是满足要求的。
何为满足要求？ 假设A（a）---B（b）---C（c）……是一个符合要求的不修改序列，括号内为下标，那么有B-A>=b-a，这样才能满足夹在中间的数能够修改。
那么本题在nlogn求最长上升子序列的基础做一些处理即可。
处于满足的序列中必须有a[i]-lis[x]-1>=i-pos[x]-1，并且替换的时候不是原来的找到大于这个值的最小的，而是找满足前面这个式子已求序列中最大的。
比如序列：1 3 6 6 13 2 8 9 10，求最长上升子序列过程中当求得的序列为 1 3 6 13 时，当遇见8时，我们不是变为1 3 6 8，而是变成1 3 8， 因为只有这样才是满足条件的，当时它的最长序列top=4不会变化。
还要注意的一点是lis[0]初始化为-oo，因为a[i]可以修改为负数。
#include<cstdio>
#include<iostream>
using namespace std; const int maxn=;
const int oo=0x3fffffff;
int a[maxn];
int lis[maxn], pos[maxn]; int main()
{
int n;
while(cin >> n)
{
for(int i=; i<=n; i++) scanf("%d",a+i);
int top=;
lis[]=-oo;
for(int i=; i<=n; i++)
{
if(a[i]>lis[top]&&a[i]-lis[top]->=i-pos[top]-)
{
lis[++top]=a[i];
pos[top]=i;
}
else
{
int l=, r=top, tp=-;
while(l<=r)
{
int mid=(l+r)>>;
if(a[i]-lis[mid]->=i-pos[mid]-)
{
tp=mid;
l=mid+;
}
else r=mid-;
}
if(tp!=-) lis[tp+]=a[i], pos[tp+]=i;
}
}
cout << n-top <<endl;
}
return ;
}
/*
5
1 6 6 7 8
7
1 2 2 2 2 2 7
9
1 3 6 6 13 2 8 9 10
13
1 2 2 3 10 6 6 6 6 6 7 8 9
11
1 2 3 4 10 10 7 8 9 10 10
*/