/*
TASK:seq
LANG:C
*/

#include <stdlib.h>
#include <stdio.h>

//ifstream fin( "seq.in" );
//ofstream fout( "seq.out" );
int n;
long a1[ 1<<20 ];
long a[ 1<<20 ];
struct interval
{ int b,f0, f1; } F[ 1<<20 ];
int t = 0;
int cmp( const void* x, const void* y )
{	int x1 = *(int*) x;
	int y1 = *(int*) y;
	if ( a1[ x1 ] != a1[ y1 ] ) return ( a1[ x1 ] - a1[ y1 ] );
	return x1 - y1;
}

void	init( )
{	int i, j;
//	fin >> n;
	scanf( "%d", &n );
	for ( i=1; i<=n; i++ ) { scanf( "%d", &a1[ i ] ); a[ i ] = i; }
	qsort( a+1, n, sizeof( long ), cmp );
	int b1 = 1;
	for ( i=1; i <= n; i++ )
	{	j = i;
		while ( a1[ a[ j ] ] == a1[ a[ i ] ] ) j++;
		F[ ++t ].b = b1;
		F[ t ].f0 = F[ t ].f1 = 999999;
		b1 = j; i = j-1;
	}
	F[ 1 ].f0 = F[ 1 ].f1 = 0;
}

inline int min( int x, int y ) { return x < y ? x : y; }

void	solve( )
{	int i, x;
 	F[ t+1 ].b = n+1;
	 for ( i=2; i<=t; i++ )
    { F[ i ].f0 = F[ i-1 ].f1 + 1;
		F[ i ].f1 = F[ i-1 ].f0 + 1;
		if ( a[ F[ i ].b ] < a[ F[ i ].b-1 ] )
		  x = 1; else  x = 0;
		if ( F[ i ].f0 > F[ i-1 ].f0 + x ) F[ i ].f0 = F[ i-1 ].f0 + x;
		if ( a[ F[ i-1 ].b ] < a[ F[ i+1 ].b-1 ] )
		  x = 1; else  x = 0;
		if ( F[ i ].f1 > F[ i-1 ].f1 + x ) F[ i ].f1 = F[ i-1 ].f1 + x;
    }
//	fout << min( F[ n ].f0, F[ n ].f1 ) << endl;
	printf( "%d\n", min( F[ t ].f0, F[ t ].f1 ) );
}

int main( )
{	init( );
	solve( );

	return 0;
}
