{
TASK:seq
LANG:PASCAL
}
program seq;

const
	MAXN					= 1000000;
	MAXN1					= 100;

type
	Integer					= LongInt;

var
	a, ind					: Array [0 .. MAXN] of Integer;
	max, min, num				: Array [0 .. MAXN] of Integer;
	used					: Array [0 .. MAXN1] of Boolean;
	c					: Array [0 .. MAXN1] of Integer;
	f					: Array [0 .. MAXN, 0 .. 1] of Integer;
	n, i, k, d				: Integer;
	answ					: Integer;
	d1, d2 {i deo}				: 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;

function inver(i: Integer): Boolean;
begin
	if (c[i] > c[i-1]) and (c[i] > c[i+1]) then inver := True
	else if (c[i] < c[i-1]) and (c[i] < c[i+1]) then inver := True
	else inver := False;
end;

procedure go(todo, cnum, cansw: Integer);
var
	i				: Integer;
	min, done			: Integer;
begin
	if (cansw > answ) then Exit;
	if (todo = n+1) then begin
		if (cansw < answ) then answ := cansw;
		Exit;
	end;
	done := -1;
	for i := 1 to n do
		if (not used[i]) and (a[i] = cnum) then begin
			done := i;
			c[todo] := i;
			used[i] := True;
			if (todo > 2) and (inver(todo-1)) then
				go(todo+1, cnum, cansw+1)
			else
				go(todo+1, cnum, cansw);

			used[i] := False;
		end;
	if (done = -1) then begin
		min := maxlongint;
		for i := 1 to n do
			if (a[i] > cnum) and (a[i] < min) then min := a[i];
		cnum := min;
		for i := 1 to n do
			if (not used[i]) and (a[i] = cnum) then begin
				c[todo] := i;
				used[i] := True;
				if (todo > 2) and (inver(todo-1)) then
					go(todo+1, cnum, cansw+1)
				else
					go(todo+1, cnum, cansw);
	
				used[i] := False;
			end;
	end;
end;

procedure Solve2;
begin
	FillChar(used, sizeof(used), 0);
	answ := maxlongint;
	go(1, -1, 0);
	writeln(answ);
end;

begin
	FillChar(f, sizeof(f), 0);
	readln(n);
	for i := 1 to n do begin 
		read(a[i]);
		ind[i] := i;
	end;
	if (n <= 60) then begin
		solve2;
		Exit;
	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;	
	min[0] := -1;
	max[0] := maxlongint;
	for i := 2 to k do begin
		if (i = 2) and (num[1] + num[2] = 2) then continue;
                if (i = 2) then begin
                	if (num[1] = 1) then begin
                        	if (min[1] > min[2]) and (min[1] < max[2]) then begin
                                	f[i, 1] := 1;
                                        f[i, 0] := 1;
                                end;
                                continue;
                        end else if (num[2] = 1) then begin
                        	if (min[2] > min[1]) and (min[2] < max[1]) then begin
                                	f[i, 1] := 1;
                                        f[i, 0] := 1;
                                end;
                                continue;
                        end;
                end;
		if (num[i] > 1) then begin
			if (num[i-1] = 1) then begin
				if (min[i-1] > min[i]) then begin
					f[i, 0] := f[i-1, 0] + 1;
                                        if (not (min[i-2] > min[i-1])) then
                                        	f[i, 0] := f[i, 0] + 1;
				end else begin
					if (max[i-2] < min[i-1]) then
						f[i, 0] := f[i-1, 0]
					else
						f[i, 0] := minv(f[i-1, 0], f[i-1, 1]) + 1;
				end;
				if (min[i-1] < max[i]) then begin
					f[i, 1] := f[i-1, 0] + 1;
                                        if (not (max[i-2] < min[i-1])) then
                                        	f[i, 0] := f[i, 0] + 1;
				end else begin
					if (min[i-2] > min[i-1]) then
						f[i, 1] := f[i-1, 1]
					else
						f[i, 1] := minv(f[i-1, 1], f[i-1, 0]) + 1;
				end;
			end else begin
				if (max[i-1] < min[i]) then f[i, 0] := f[i-1, 0]
				else f[i, 0] := minv(f[i-1, 0], f[i-1, 1]) + 1;
				if (min[i-1] > max[i]) then f[i, 1] := f[i-1, 1]
				else f[i, 1] := minv(f[i-1, 0], f[i-1, 1]) + 1;
			end;
		end else begin
			if (num[i-1] = 1) then begin
				if (min[i-1] > min[i]) then begin
					if (min[i-2] > min[i-1]) then f[i, 0] := f[i-1, 1]
					else f[i, 0] := minv(f[i-1, 0], f[i-1, 1]) + 1;
				end else begin
					if (max[i-2] < min[i-1]) then f[i, 0] := f[i-1, 0]
					else f[i, 0] := minv(f[i-1, 0], f[i-1, 1]) + 1;
				end;
			end else begin
				if (max[i-1] > min[i]) then d1 := 1 else d1 := 0;
				if (min[i-1] < min[i]) then d2 := 1 else d2 := 0;
				f[i, 0] := minv(f[i-1, 0] + d1, f[i-1, 1] + d2);
			end;
			f[i, 1] := f[i, 0];
		end;
	end;
	writeln(minv(f[k, 0], f[k, 1])-1);
end.