翼支付编程大赛――修改数列

题目详情（修改数列）：

我们有1个数列。我们可以把其中的任意1些项替换成其他的正整数，但是我们不能删掉项，也不能交换项的顺序。请问最少需要几次替换，才能把数列变成严格单调递增的？

输入格式

多组数据，每组数据第1行1个正整数n (n<=1000000)

每组数据第2行是n个空格分隔的非负整数,每一个不超过10^9，表示数列中的数。

输出格式

对每组数据，输出1行，包括其最少的替换次数。

答题说明:

<pre name="code" class="java">import java.util.Scanner;  
  
public class Main {    
    public static void main(String[] args) {  
        Scanner in = new Scanner(System.in);  
        int n;  
        int[] num;  
        while(in.hasNext()){  
            n = in.nextInt();
            num = new int[n];
            for(int i = 0; i < n; i++)
            	num[i] = in.nextInt();
            int len = 0;
            for(int i = n; i > 0; i--){//暴力破解！！
            	int tmp = lis(num, i);
            	len = tmp > len ? tmp : len;
            }
            System.out.println(n-len);
        }
    }  
  
    private static int lis(int[] num, int n) {
		// TODO Auto-generated method stub
		int[] bnum = new int[n];
		int[] bpos = new int[n];
		int init;	//从后到前，第1个元素值大于等于下标（从0开始）的元素为首
		int len;	//最长严格单音调串长度
		for(init = n - 1; init >= 0; init--){
			if(num[init] >= init){
				bnum[0] = num[init];
				bpos[0] = init;
				break;
			}
		}
		len = 1;
		if(init < 0){
			return 1;
		}
		for(int i = init - 1; i >= 0; i--){
			if(num[i] >= i){	//值大于等于下标才有比较的意义
				if(bnum[len - 1] - num[i] >= bpos[len - 1] - i){    
				//值的差大于等于下标的差才可以添加
					bnum[len] = num[i];
					bpos[len++] = i;
				}else if(num[i] > bnum[len - 1]){
					int pos = find(bnum, bpos, len, num[i], i);	
					//寻觅替换位置
					if(pos != ⑴){
						bnum[pos] = num[i];
						bpos[pos] = i;
					}
				}
			}
		}
		return len;
	}

	private static int find(int[] bnum, int[] bpos, int len, int number, int pos) {
		// TODO Auto-generated method stub
		int i = 0;
		for(i = len - 1; i > 0; i--){	//找到恰好比number大的元素位置
			if(bnum[i - 1] > number){
				break;
			}
		}
		if(i <= 0)
			return 0;
		else{
			if(bnum[i - 1] - number >= bpos[i - 1] - pos)	//判断替换可行否
				return i;
			else
				return ⑴;
		}
	}
}