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
#include <iostream>
#include <limits>
#include <numeric>
#include <utility>
#include <vector>

using namespace std;

constexpr int INF = numeric_limits<int>::max();

struct Helper {
	int cnt;
	int prev;
	int up;
	bool prev_changed;
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	vector<int> v{};

	cin >> n;
	v.resize(n);

	for(auto& e : v) {
		cin >> e;
	}

	int res = INF;

	for(int i = 0; i < 2; i++) {
		res = min(res, accumulate(
			v.begin() + 1,
			v.end(),
			Helper { 0, v[0], i },
			[](Helper const& acc, int curr) {
				bool change;

				if(acc.prev_changed) {
					change = false;
				} else if(acc.up) {
					change = curr <= acc.prev;
				} else {
					change = curr >= acc.prev;
				}

				return Helper { acc.cnt + change , (change ? acc.prev : curr), !acc.up, change };
			}
		).cnt);
	}

	cout << res;

	return 0;
}