#include<stdio.h>

int N;
int A[30000];

void input()
{
	int i;
	scanf("%d",&N);
	for(i=0;i<N;i++)
		scanf("%d",&A[i]);
}

int bs1(int B[],int len,int x)
{
	int b,e,m;
	b=0; e=len;
	while(b<e)
	{
		m=(b+e)/2;
		if(B[m] > x)
			e=m;
		else
			b=m+1;
	}
	return b;
}

int LIS()
{
	int i,j;
	int len;
	int B[30000];
	B[0]=A[0]; len=1;
	for(i=1;i<N;i++)
	{
		if(A[i]>=B[len-1])
			B[len++]=A[i];
		else
		{
			j=bs1(B,len,A[i]);
			B[j]=A[i];
		}
	}
	return len;
}

void swap()
{
	int i,j,t;
	i=0; j=N-1;
	while(i<j)
	{
		t=A[i];
		A[i]=A[j];
		A[j]=t;
		i++; j--;
	}
}

void output()
{
	int l1,l2;
	l1=LIS();
	swap();
	l2=LIS();
	printf("%d\n",N-(l1 > l2 ? l1 : l2));
}

int main()
{
	input();
	output();
	return 0;
}