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

static uint64_t test(std::vector<int64_t> &a, bool larger) {
    uint64_t no = 0, yes = 1;
    for (uint64_t i = 1; i < a.size(); ++i) {
        // no -> yes, yes -> no
        uint64_t next_no = yes, next_yes = no + 1;

        // yes -> yes
        if (next_yes > yes + 1) { next_yes = yes + 1; }

        // no -> no
        // larger
        if (larger && a[i] > a[i - 1]) { next_no = no; }
        // !larger
        if (!larger && a[i] < a[i - 1]) { next_no = no; }

        no = next_no; yes = next_yes;
        larger = !larger;
    }

    return std::min(no, yes);
}

int main() {
    uint64_t n;
    std::cin >> n;

    std::vector<int64_t> a(n);
    for (uint64_t i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    uint64_t r1 = test(a, true);
    uint64_t r2 = test(a, false);
    std::cout << std::min(r1, r2) << "\n";
}