題目詳情（修改數列）：

我們有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 ⑴;
		}
	}
}