hackerrank.com/challenges/modify-the-sequence

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#include <iostream>
using namespace std;

#define MAX 1000001
int x[MAX+1],n;

int LISlast[MAX+1];
int LNDS(int *x, int n){
    int l=0,*p;
    LISlast[0]=-1;
    for (int i=0; i<n; i++){

    if (x[i]<=0) continue;   // ONLY POSITIVE NUMBERS ALLOWED

        p=upper_bound(LISlast,LISlast+l,x[i]);
        if (p==LISlast+l) ++l;
        *p=x[i];
    }
    return l;
}

int main() {
    cin>>n;
    for (int i=0; i<n; i++){
        cin>>x[i]; x[i]-=i;
    }
    cout<<n-LNDS(x,n)<<endl;
    return 0;
}