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
#include <cstdio>

const int N = 50000 + 9;

int v[N];
int r[N][4];

int myMin(int a, int b) { return a <= b ? a : b; }

bool okMin(int i) {
	if (i % 2 == 0) if (v[i] < v[i+1]) return true;
	if (i % 2 != 0) if (v[i] > v[i+1]) return true;
	return false;
}

bool okMax(int i) {
	if (i % 2 == 0) if (v[i] > v[i+1]) return true;
	if (i % 2 != 0) if (v[i] < v[i+1]) return true;
	return false;
}

int solve(int n) {
	r[0][0] = v[0] < v[1] ? 0 : 1;
	r[0][1] = 0;
	r[0][2] = v[0] > v[1] ? 0 : 1;
	r[0][3] = 0;

	for (int i=1; i<n; ++i) {
		r[i][0] = myMin(r[i-1][1] + 1, okMin(i) ? r[i-1][0] : N);
		r[i][1] = myMin(r[i-1][1] + 1, r[i-1][0]);
		r[i][2] = myMin(r[i-1][3] + 1, okMax(i) ? r[i-1][2] : N);
		r[i][3] = myMin(r[i-1][3] + 1, r[i-1][2]);
	}

	return myMin(r[n-1][1], r[n-1][3]);
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i=0; i<n; ++i) scanf("%d", v + i);

	int res = solve(n);
	printf("%d\n", res);

	return 0;
}