求最少改变几个数，使得序列变成最长上升子序列。

【题解】

可以修改的条件：$a_j-a_i \leq j-i (j<i)$ 即 $a_j-j \leq a_i-i$，那么把$a_i$变为$a_i-i$即可。

然后套用求LIS的nlogn方法。

# include <stdio.h>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

int f[100010];
int n, a[100010], c[100010];

int main() {
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) {
		scanf("%d", &a[i]);
		a[i] = a[i] - i;
	}

	f[1] = 1;
	// 这是普通的 O(n^2) 做法
	/* 
	for (int i=2; i<=n; ++i)
		for (int j=1; j<i; ++j)
			if(f[j]+1 > f[i] && a[i] >= a[j])	
				f[i] = f[j]+1;
	*/
	a[n+1] = 2147483647; 
	int ans = 1;
	c[1] = 1;
	for (int i=2; i<=n; ++i) c[i] = n+1; 
	for (int i=2; i<=n; ++i) {
		int l=1, r=ans, anst = 0;
		while(1) {
			if(r-l<=3) {
				for (int j=r; j>=l; --j)
					if (a[c[j]] <= a[i]) {
					 	anst = c[j];
						break;
					}
				break;
			}
			int mid = l+r>>1;
			if(a[c[mid]] <= a[i]) l = mid;
			else r = mid; 
		}
		f[i] = f[anst] + 1;
		if(a[c[f[i]]] > a[i])
			c[f[i]] = i; 
		ans = max(ans, f[i]); 
	}
	printf("%d\n", n-ans);
	return 0;
}