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


int M_INF = -1000*1000*1000;
int P_INF =  1000*1000*1000;
int N_MAX = 50 * 1000;


int policz(std::vector<bool> &didInc, std::vector<bool> &didDec, int n) {
    std::vector<int> kon0, kon1;
    kon0.reserve(N_MAX);
    kon1.reserve(N_MAX);
    
    kon0[0] = didDec[0] ? 0 : 1;
    kon1[0] = didInc[0] ? 0 : 1;

    bool change0, change0o, change1;
    change0 = !didDec[0];
    change1 = !didInc[0];
    
//    std::cout << "kon0[" << 0 << "] = " << kon0[0] << std::endl;
//    std::cout << "kon1[" << 0 << "] = " << kon1[0] << std::endl;
//
//    std::cout << "didInc[" << 0 << "] = " << (didInc[0] ? "true" : "false") << std::endl;
//    std::cout << "didDec[" << 0 << "] = " << (didDec[0] ? "true" : "false") << std::endl;
//
//    std::cout << "change0 = " << (change0 ? "true" : "false") << std::endl;
//    std::cout << "change1 = " << (change1 ? "true" : "false") << std::endl;

    for (int i = 1; i < n - 1; i++) {
        kon0[i] = kon1[i - 1] + ((didDec[i] || change1) ? 0 : 1);
        kon1[i] = kon0[i - 1] + ((didInc[i] || change0) ? 0 : 1);

        change0o = change0;
        change0 = !(didDec[i] || change1);
        change1 = !(didInc[i] || change0o);
        
//        std::cout << "kon0[" << i << "] = " << kon0[i] << std::endl;
//        std::cout << "kon1[" << i << "] = " << kon1[i] << std::endl;
//        std::cout << "didInc[" << i << "] = " << (didInc[i] ? "true" : "false") << std::endl;
//        std::cout << "didDec[" << i << "] = " << (didDec[i] ? "true" : "false") << std::endl;
//        std::cout << "change0 = " << (change0 ? "true" : "false") << std::endl;
//        std::cout << "change1 = " << (change1 ? "true" : "false") << std::endl;
    }
    
    return std::min(kon0[n-2], kon1[n-2]);
}

int main() {
    std::ios::sync_with_stdio(false);

    std::vector<bool> didInc, didDec;

    didInc.reserve(N_MAX);
    didDec.reserve(N_MAX);


    int n, prev, current;
    std::cin >> n;
    std::cin >> prev;

    for (int i = 1; i < n; i++) {
        std::cin >> current;
        didInc[i - 1] = (current > prev);
        didDec[i - 1] = (current < prev);
        prev = current;
    }

    std::cout << policz(didInc, didDec, n) << std::endl;

    return 0;
}

//
//int main() {
//    std::vector<bool> didInc = { false, false, false };
//    std::vector<bool> didDec = { false, false, false };
//    int n = 4;
//
//    std::cout << policz(didInc, didDec, n) << std::endl;
//}