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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#include <stdlib.h>

int main()
{
int N,n,*R,*D,Y,LH,cLH,HL,cHL;

	scanf("%d",&N);
	R = (int*) malloc(N*sizeof(int));
	for (n = 0; n < N; n++) scanf("%d",R+n);
	
//	for (n = 0; n < N; n++) printf("%d\t",R[n]);
//	printf("\n");

		
	LH = cLH = HL = cHL = 0;
	for (n = 1; n < N; n++)
	{
//		printf("%d %c %d\n",R[n-1],(n&1)==1?'>':'<',R[n]);	
		if ((n&1) == 1 && R[n-1] <= R[n]) cLH++;
		else if ((n&1) == 0 && R[n-1] >= R[n]) cLH++;
		else
		{
			LH += cLH % 2;
			LH += cLH >> 1;
			cLH = 0;
		}
		if ((n&1) == 1 && R[n-1] >= R[n]) cHL++;
		else if ((n&1) == 0 && R[n-1] <= R[n]) cHL++;
		else
		{
			HL += cHL % 2;
			HL += cHL >> 1;
			cHL = 0;
		}
	}
//	printf("HL=%d, cHL=%d\n",HL,cHL);
//	printf("LH=%d, cLH=%d\n",LH,cLH);
	HL += cHL % 2;
	HL += cHL >> 1;
	LH += cLH % 2;
	LH += cLH >> 1;
	
	printf("%d\n",(HL<LH)?HL:LH);
	
	free(R);
//	free(D);
		
	return 0;
}