Modify The Sequence

                            Solution in C :

In C++ :





#include <iostream>
#include <ctime>
#include <fstream>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <utility>
#include <cctype>
#include <list>

using namespace std;

#define FORALL(i,a,b) for(int i=(a);i<=(b);++i)
#define FOR(i,n) for(int i=0;i<(n);++i)
#define FORB(i,a,b) for(int i=(a);i>=(b);--i)

typedef long long ll;
typedef long double ld;
typedef complex<ld> vec;

typedef pair<int,int> pii;
typedef map<int,int> mii;

#define pb push_back
#define mp make_pair

#define INF 2000000001
#define MAXN 1000100
int A[MAXN];
int dp[MAXN];

int main() {
	int N;
	cin >> N;
	A[0] = 1;
	FORALL(i,1,N) scanf("%d",A+i);
	FORALL(i,1,N) A[i] -= i;
	FORALL(i,0,N) dp[i] = INF;
	//FORALL(i,1,N) cout << A[i] << " "; cout << endl;
	dp[0] = 0;
	FORALL(i,1,N) {
		if (A[i] < 0) continue;
		int idx = upper_bound(dp,dp+N,A[i]) - dp - 1;
		//cout << i <<  " " << A[i] << " " << idx << endl;
		assert(idx >= 0);
		dp[idx+1] = A[i];
	}
	/*
	FOR(i,N) cout << A[i] << endl;
	*/
	int ans = 0;
	FORALL(i,0,N) if (dp[i] < INF) ans = max(ans,i);
	/*
	FORALL(i,0,N) {
		cout << i << " " << dp[i] << endl;
	}*/
	
	cout << N-ans << endl;
}








In Java :





import java.io.*;
import java.util.*;

public class Solution {

	BufferedReader br;
	PrintWriter out;
	StringTokenizer st;
	boolean eof;

	void solve() throws IOException {
		int n = nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt() - i;
		}
		
		int[] d = new int[n + 1];
		Arrays.fill(d, Integer.MAX_VALUE);
		d[0] = Integer.MIN_VALUE;
		
		int ans = 0;
		for (int i = 0; i < n; i++) {
			int x = a[i];
			if (x <= 0)
				continue;
			int l = 0;
			int r = ans + 1;
			while (r - l > 1) {
				int mid = (l + r) >> 1;
				if (d[mid] > x) {
					r = mid;
				} else {
					l = mid;
				}
			}
			if (r == ans + 1) {
				ans++;
			}
			d[r] = x;
		}
		
		out.println(n - ans);
	}

	Solution() throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	public static void main(String[] args) throws IOException {
		new Solution();
	}

	String nextToken() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				eof = true;
				return null;
			}
		}
		return st.nextToken();
	}

	String nextString() {
		try {
			return br.readLine();
		} catch (IOException e) {
			eof = true;
			return null;
		}
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}








In C :





#include <stdio.h>
#include <string.h>
//using namespace std;
const int inf = 2000000000;
int a[1000005];
int longest;

void find(int x) { 
int left = 1, right = longest;
    while (left <= right) {

        int mid = (left + right) >> 1;
        if (a[mid] <= x) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    a[++right] = x;
    if (right > longest) {
        longest =right;
    }
}

int main() {
int n;
    scanf("%d",&n);
    for (int i = 0; i <= n; ++i) {
        a[i] = inf;
    }
    longest = 0; 
    for (int i = 1; i <= n; ++i) {      
        int x;  
        scanf("%d",&x);
        if ((x -= i) >= 0) {
            find(x);
        }
    }
    printf("%d\n", n - longest);
    return 0;


}








In Python3 :






import bisect

def parse(seq):
    for i in range(len(seq)):
        seq[i] -= i

def patience_sort(array):
    piles = [array[0]]
    for x in range(1, len(array)):
        i = bisect.bisect_right(piles, array[x])
        if i != len(piles):
            piles[i] = array[x]
        else:
            piles.append(array[x])
    return len(piles)

def main():
    n = int(input())
    array = [i for i in range(-99, 1)] + list(map(int, input().split()))
    parse(array)
    #print(array)
    print(n - patience_sort(array) + 100)

if __name__ == '__main__':
    main()