#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=300005;
int a[N],b[N],c[N];//b[N],c[N]分别为lis，lds
int n;
int main()
{
	int li,ld,i;//li,ld为lis，lds长度
	int n;
	cin>>n;
	li=ld=1;
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	b[1]=c[1]=a[0];
	for(i=1;i<n;i++)
	{
		int x1,x2,x,mid;
		x1=1;
		x2=li;
		x=a[i];
		while(x1<=x2)
		{
			mid=(x1+x2)/2;
			if(b[mid]<x&&b[mid+1]>x)
				break;
			if(b[mid]>x)
				x2=mid-1;
			else if(b[mid]<=x)
				x1=mid+1;
		}
		if(b[li]<=x)
		{
			li++;
			b[li]=x;
		}
		else if(x1<=x2)
			b[mid+1]=x;
		else if(b[x1]>x)
			b[x1]=x;
	}
	for(i=1;i<n;i++)
	{
		int x1,x2,x,mid;
		x1=1;
		x2=ld;
		x=a[i];
		while(x1<=x2)
		{
			mid=(x1+x2)/2;
			if(c[mid]>x&&c[mid+1]<x)
				break;
			if(c[mid]<=x)
				x2=mid-1;
			else
				x1=mid+1;
		}
		if(c[ld]>=x)
		{
			ld++;
			c[ld]=x;
		}
		else if(x1<=x2)
			c[mid+1]=x;
		else if(c[x1]<x)
			c[x1]=x;
	}
	if(li>ld)
		ld=li;
	cout<<n-ld<<endl;
	return 0;
}