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

using namespace std;

int dp[2][2][50500]; // na miejscu / nie, dół / góra

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	int last, a;
	cin >> last;
	dp[1][0][0] = 1;
	dp[1][1][0] = 1;
	for(int i = 1; i < n; i++) {
		cin >> a;
		dp[0][0][i] = dp[1][1][i - 1];
		dp[1][0][i] = min(dp[1][1][i - 1], dp[0][1][i - 1]) + 1;
		dp[0][1][i] = dp[1][0][i - 1];
		dp[1][1][i] = min(dp[1][0][i - 1], dp[0][0][i - 1]) + 1;
		if (a > last) {
			dp[0][0][i] = min(dp[0][0][i], dp[0][1][i - 1]);
		}
		if (a < last) {
			dp[0][1][i] = min(dp[0][1][i], dp[0][0][i - 1]);
		}
		last = a;
	}
	cout << min(min(dp[0][0][n - 1], dp[1][0][n - 1]), min(dp[0][1][n - 1], dp[1][1][n - 1]));
}