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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
int n;
int former;
int current;
int liczby[50001];
bitset<50001> delta;
const int M = 1e9;
int r1, r2;



int program(){
	int counter = 0;
	for(int i = 2; i < n; i++){
		current = liczby[i];
		if(current == former){
			if(delta[i-2] == 1){
				current = -M;
				delta[i-1] = 0;
				counter += 1;
				//cout << i << endl;
			}
			else{
				current = M;
				delta[i-1] = 1;
				counter += 1;
				//cout << i << endl;
			}
		}
		else{
			delta[i-1] = (current - former > 0);
			if(delta[i-1] == delta[i-2]){
				if(delta[i-2] == 1){
					current = -M;
					delta[i-1] = 0;
					counter += 1;
					//cout << i << endl;
				}
				else{
					current = M;
					delta[i-1] = 1;
					counter += 1;
					//cout << i << endl;
				}
			}
		}
		former = current;
		
	}
	return counter;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> liczby[i];
		//cout << liczby[i] << " ";
	}
	//cout << endl;
	former = liczby[0];
	current = liczby[1];
	if(current == former){
		delta[0] = 1;
		former = M;
		r1 = program();
		delta[0] = 0;
		former = -M;
		r2 = program();
		cout << min(r1, r2) + 1;
		return 0;
	}
	delta[0] = (current - former > 0);
	former = current;
	r1 = program();
	if(delta[0] == 0){
		delta[0] = 1;
		former = M;
		r2 = program();
	}
	else{
		delta[0] = 0;
		former = -M;
		r2 = program();
	}
	r2 += 1;
	cout << min(r1, r2);
	return 0;
}