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

namespace {
    using std::cin;
    using std::cout;
    using std::min;
    using notes_t = std::vector<int32_t>;

    int32_t const MIN_INS = -1000000000;
    int32_t const MAX_INS =  1000000000;

    bool is_up(notes_t const & notes, size_t k) noexcept {
        if ( (k % 2 == 0 && notes[k - 1] > notes[k]) ||
             (k % 2 == 1 && notes[k - 1] < notes[k]) )
            return true;
        return false;
    }

    bool is_down(notes_t const & notes, size_t k) noexcept {
        if ( (k % 2 == 0 && notes[k - 1] < notes[k]) ||
             (k % 2 == 1 && notes[k - 1] > notes[k]) )
            return true;
        return false;
    }

    size_t count_changes(notes_t & notes, bool up) {
        size_t result = 0;
        for (size_t k = 1; k < notes.size(); ++k) {
            if (up ? !is_up(notes, k) : !is_down(notes, k)) {
                ++result;
                if (k % 2 == 0)
                    notes[k] = up ? MIN_INS : MAX_INS;
                else
                    notes[k] = up ? MAX_INS : MIN_INS;
            }
        }
        return result;
    }
}   /* anonymous namespace */

 int main() {
    size_t n, result = 0;
    int32_t note;
    notes_t notes;
    size_t alt_up_cnt = 0, alt_down_cnt = 0;

    cin >> n;
    for (size_t k = 0; k < n; ++k) {
        cin >> note;
        notes.push_back(note);
        if (k > 0) {
            if (is_up(notes, k)) {
                ++alt_up_cnt;
            } else if (is_down(notes, k)) {
                ++alt_down_cnt;
            }
         }
    }

    if (alt_up_cnt > alt_down_cnt) {
        result = count_changes(notes, true);
    } else if (alt_up_cnt < alt_down_cnt) {
        result = count_changes(notes, false);
    } else {
        notes_t  notes_cpy(notes);
        result = min(count_changes(notes, true), count_changes(notes_cpy, false));
    }

    cout << result << '\n';
    return 0;
}