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


int main() {
    std::ios_base::sync_with_stdio(0);

    int n;
    std::cin >> n;

    std::vector<int> dp[2][2];  // [0 - first INC, 1 - first DEC], [0 - last unchanged, 1 - last changed to INF or -INF)
    dp[0][0].resize(n); dp[1][0].resize(n); dp[0][1].resize(n); dp[1][1].resize(n);
    dp[0][0][0] = 0; dp[1][0][0] = 0;
    dp[0][1][0] = 1; dp[1][1][0] = 1;

    int last;
    for (int i = 0; i < n; ++i) {
        int cur;
        std::cin >> cur;

        if (i > 0) {
            int m = i % 2;
            dp[m][0][i] = (last > cur ? dp[m][0][i - 1] : dp[m][1][i - 1]);
            dp[!m][0][i] = (last < cur ? dp[!m][0][i - 1] : dp[!m][1][i - 1]);
            dp[m][1][i] = dp[m][0][i - 1] + 1;
            dp[!m][1][i] = dp[!m][0][i - 1] + 1;
            dp[m][0][i] = std::min(dp[m][0][i], dp[m][1][i]);
            dp[!m][0][i] = std::min(dp[!m][0][i], dp[!m][1][i]);
        }

        last = cur;
    }
    std::cout << std::min(dp[0][0][n - 1], dp[1][0][n - 1]);
    return 0;
}