1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
const int N=50005,inf=1000000000;
int n,i,j,k,o,x,y,w,ans,a[N],f[N][3];
inline void up(int&a,int b){a<b?(a=b):0;}
inline int get(int x,int y){
	if(y==1)return -inf;
	if(y==2)return inf;
	return a[x];
}
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(i=0;i<2;i++){
		for(j=1;j<=n;j++)a[j]*=-1;
		for(j=1;j<=n;j++)for(k=0;k<3;k++)f[j][k]=-1;
		for(k=0;k<3;k++)f[1][k]=k==0;
		for(j=1;j<n;j++)for(k=0;k<3;k++){
			w=f[j][k];
			if(w<0)continue;
			x=get(j,k);
			for(o=0;o<3;o++){
				y=get(j+1,o);
				if(j&1){
					if(x<=y)continue;
				}else{
					if(x>=y)continue;
				}
				up(f[j+1][o],w+(o==0));
			}
		}
		for(k=0;k<3;k++)up(ans,f[n][k]);
	}
	printf("%d",n-ans);
}