{
TASK:seq
LANG:PASCAL
}
program seq;

const
	MAXN					= 1000000;

type
	Integer					= LongInt;

var
	a, ind					: Array [1 .. MAXN] of Integer;
	max, min, num				: Array [1 .. MAXN] of Integer;
	f					: Array [1 .. MAXN, 0 .. 1] of Integer;
	n, i, k, d				: Integer;

procedure qsort(l, r: Integer);
var
  	i, j, x, y				: Integer;
begin
  	i := l; j := r; x := a[(l+r) DIV 2];
  	repeat
    		while (a[i] < x) do i := i + 1;
    		while (x < a[j]) do j := j - 1;
    		if (i <= j) then begin
      			y := a[i]; a[i] := a[j]; a[j] := y;
			y := ind[i]; ind[i] := ind[j]; ind[j] := y;
      			i := i + 1; j := j - 1;
    		end;
  	until (i > j);
  	if (l < j) then qsort(l, j);
  	if (i < r) then qsort(i, r);
end;

function minv(a, b: Integer): Integer;
begin
	if (a > b) then minv := b else minv := a;
end;

begin
	FillChar(f, sizeof(f), 0);
	readln(n);
	for i := 1 to n do begin 
		read(a[i]);
		ind[i] := i;
	end;
	qsort(1, n);
	for i := 1 to n do begin
		min[i] := maxlongint;
		max[i] := -1;		{ estestveni chisla?? }
	end;
	i := 1;
	k := 0;
	while (i <= n) do begin
		k := k + 1;
		min[k] := ind[i];
		max[k] := ind[i];
		num[k] := 1;
		while (i < n) and (a[i+1] = a[i]) do begin
			i := i + 1;
			num[k] := num[k] + 1;
			if (ind[i] > max[k]) then max[k] := ind[i];
			if (ind[i] < min[k]) then min[k] := ind[i];
		end;
		i := i + 1;
	end;	
	for i := 2 to k do begin

        	if (i > 2) and (num[i-1] = 1) and (num[i-2] = 1) then begin
                	if (num[i] = 1) then begin
                        	if (min[i-1] > min[i-2]) and (min[i-1] > min[i]) then
                                	f[i, 0] := f[i-1, 0] + 1
                                else if (min[i-1] < min[i-2]) and (min[i-1] < min[i]) then
                                	f[i, 0] := f[i-1, 0] + 1
                                else
                                	f[i, 0] := f[i-1, 0];
                                f[i, 1] := f[i, 0];
                        end else begin
                        	if (not ((min[i-2] < min[i-1]) and (min[i-1] < min[i]))) then
                                	f[i, 0] := f[i-1, 0] + 1
                                else
                                	f[i, 0] := f[i-1, 0];
                                if (not ((min[i-2] > min[i-1]) and (min[i-1] > max[i]))) then
                                	f[i, 1] := f[i-1, 0] + 1
                                else
                                	f[i, 1] := f[i-1, 0];

                        end;
                        continue;
                end;

		if (num[i] = 1) then begin
			if (num[i-1] = 1) then begin
				f[i, 0] := f[i-1, 0];
				f[i, 1] := f[i, 0];
			end else begin
				if (min[i-1] < min[i]) then
					f[i, 0] := f[i-1, 1] + 1;
				if (max[i-1] > max[i]) then d := 1 else d := 0;
				f[i, 0] := minv(f[i, 0], f[i-1, 0] + d);
				f[i, 1] := f[i, 0];
			end;
		end else begin
			if (num[i-1] = 1) then begin
				if (min[i-1] > min[i]) then 
					f[i, 0] := f[i-1, 0] + 1
				else
					f[i, 0] := f[i-1, 0];
				if (min[i-1] < max[i]) then 
					f[i, 1] := f[i-1, 0] + 1
				else
					f[i, 1] := f[i-1, 0];
			end else begin
				if (max[i-1] < min[i]) then d := 0 else d := 1;
				f[i, 0] := f[i-1, 0] + d;
				f[i, 0] := minv(f[i, 0], f[i-1, 1] + 1);
				if (min[i-1] > max[i]) then d := 0 else d := 1;
				f[i, 1] := f[i-1, 1] + d;
				f[i, 1] := minv(f[i, 1], f[i-1, 0] + 1);
			end;
		end;
	end;
	writeln(minv(f[k, 0], f[k, 1]));
end.