View Code of Problem 4064

#include<iostream>
#include<string.h>
using namespace std;
int main(){
	int N;
	while(cin>>N){
		int a[N];
		for(int i=0;i<N;i++){
			cin>>a[i];
		}
		int Sdp[140],Cdp[140];
		memset(Sdp,0,sizeof(Sdp));
		memset(Cdp,0,sizeof(Cdp));
		for(int i=0;i<N;i++){
			Sdp[i]=1;
			for(int j=0;j<i;j++){
				if(a[j]<a[i]){
					Sdp[i]=max(Sdp[i],Sdp[j]+1);
					//cout<<Sdp[i]<<endl;
				}
			}
		}
		for(int i=N-1;i>=0;i--){
			Cdp[i]=1;
			for(int j=N-1;j>i;j--){
				if(a[j]<a[i]){
					Cdp[i]=max(Cdp[i],Cdp[j]+1);
				}
			}
		}
		int ma=0;
		for(int i=0;i<N;i++){
			if(Cdp[i]+Sdp[i]-1>ma){
				ma=Cdp[i]+Sdp[i]-1;
			}
		}
		cout<<N-ma<<endl;
	}
}