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

using namespace std;

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

    int N;
    cin >> N;
    vector<int> A(N, 0);
    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        A[i] = a;
    }

    int dp[4] = {0, 0, 1, 1};
    // 0 -- UP no change
    // 1 -- DOWN no change
    // 2 -- UP MAX LIMIT
    // 3 -- DOWN MIN LIMIT
    for (int i = 1; i < N; ++i) {
        int dp1[4] = {};

        dp1[0] = dp[3];
        if (A[i - 1] < A[i]) dp1[0] = min(dp1[0], dp[1]);

        dp1[1] =  dp[2];
        if (A[i - 1] > A[i]) dp1[1] = min(dp1[1], dp[0]);

        dp1[2] = min(dp[1], dp[3]) + 1;
        dp1[3] = min(dp[0], dp[2]) + 1;

        dp[0] = dp1[0];
        dp[1] = dp1[1];
        dp[2] = dp1[2];
        dp[3] = dp1[3];
    }

    cout << min(min(min(dp[0], dp[1]), dp[2]), dp[3]) << "\n";

    return 0;
}