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

int countChangeIfNecessary(
        int firstVoice,
        int secondVoice,
        bool firstIsLower
) {
    if (firstIsLower && firstVoice < secondVoice) return 0;
    else return 1;
}

int countChangeIfNecessary(
        int firstVoice,
        int secondVoice,
        int thirdVoice,
        bool firstIsLower
) {
    if (firstIsLower) {
        if (firstVoice < secondVoice && secondVoice > thirdVoice) return 0;
        else return 1;
    } else {
        if (firstVoice > secondVoice && secondVoice < thirdVoice) return 0;
        else return 1;
    }
}

int countNecessaryChanges(
        int n,
        int voices[],
        bool firstIsLower
) {
    int necessaryChanges = 0;
    int index;
    for (int i = 1; i <= n; i += 2) {
        index = i - 1;

        //last voice left
        if (i == n) continue;

        if (i == n - 1) {
            //last two voices left
            necessaryChanges += countChangeIfNecessary(
                    voices[index],
                    voices[index + 1],
                    firstIsLower
            );
        } else {
            //more than two voices left
            necessaryChanges += countChangeIfNecessary(
                    voices[index],
                    voices[index + 1],
                    voices[index + 2],
                    firstIsLower
            );
        }
    }
    return necessaryChanges;
}

int main() {
    std::string line1;
    std::getline(std::cin, line1);
    int n = std::stoi(line1);

    std::string line2;
    std::getline(std::cin, line2);

    int voices[n];
    int lastIndex = 0;
    int index;

    std::string voiceString;
    for (int i = 0; i < n; i++) {
        index = line2.find(' ', lastIndex + 1);
        voiceString = line2.substr(lastIndex, index - lastIndex);
        voices[i] = std::stoi(voiceString);
        lastIndex = index;
    }

    int necessaryChangesFirstIsLower = countNecessaryChanges(n, voices, true);
    int necessaryChangesFirstIsGreater = countNecessaryChanges(n, voices, false);

    int result = std::min(necessaryChangesFirstIsLower, necessaryChangesFirstIsGreater);
    std::cout << result;
}