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

const int N = 50005;
int n, d[N][3][2];

int prev[3] = {0, -1000000000, 1000000000};
int cur[3] = {0, -1000000000, 1000000000};

int main() {
	scanf("%d", &n);
	memset(d, 0x3f, sizeof d);
	d[0][1][0] = d[0][2][1] = 0;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", cur);
		for (int j = 0; j < 3; ++j) {
			for (int k = 0; k < 3; ++k) {
				if (prev[j] < cur[k]) d[i][k][1] = std::min(d[i][k][1], d[i - 1][j][0] + (bool)k);
				if (prev[j] > cur[k]) d[i][k][0] = std::min(d[i][k][0], d[i - 1][j][1] + (bool)k);
			}
		}
		prev[0] = cur[0];
	}
	int ans = ~(1 << 31);
	for (int i = 0; i < 3; ++i) for (int j = 0; j < 2; ++j) ans = std::min(ans, d[n][i][j]);
	printf("%d\n", ans);
	return 0;
}