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
#include <iostream>
#include <vector>
using namespace std;

vector<long long> a, hilo, hieq, eqhi, eqeq, eqlo, lohi, loeq;

int main() {
    int n;
    cin >> n;
    a.resize(n + 1);
    hilo.resize(n + 1);
    hieq.resize(n + 1);
    eqhi.resize(n + 1);
    eqeq.resize(n + 1);
    eqlo.resize(n + 1);
    lohi.resize(n + 1);
    loeq.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    hilo[2] = 2;
    hieq[2] = 1;
    eqhi[2] = 1;
    eqeq[2] = 0;
    if (a[1] == a[2]) {
        eqeq[2] = 1000007;
    }
    eqlo[2] = 1;
    lohi[2] = 2;
    loeq[2] = 1;
    for (int i = 2; i <= n; i++) {
        if (i > 2) {
            hilo[i] = min(lohi[i - 1], eqhi[i - 1]) + 1;
            lohi[i] = min(hilo[i - 1], eqlo[i - 1]) + 1;
            hieq[i] = min(lohi[i - 1], eqhi[i - 1]);
            loeq[i] = min(hilo[i - 1], eqlo[i - 1]);

            if (a[i - 2] < a[i - 1]) {
                eqhi[i] = hieq[i - 1] + 1;
                eqlo[i] = min(eqeq[i - 1], loeq[i - 1]) + 1;
                if (a[i - 1] < a[i]) {
                    eqeq[i] = hieq[i - 1];
                } else if (a[i - 1] == a[i]) {
                    eqeq[i] = 1000007;
                } else {
                    eqeq[i] = min(eqeq[i - 1], loeq[i - 1]);
                }
            } else if (a[i - 2] == a[i - 1]) {
                eqhi[i] = hieq[i - 1] + 1;
                eqlo[i] = loeq[i - 1] + 1;
                if (a[i - 1] < a[i]) {
                    eqeq[i] = hieq[i - 1];
                } else if (a[i - 1] == a[i]) {
                    eqeq[i] = 1000007;
                } else {
                    eqeq[i] = loeq[i - 1];
                }
            } else {
                eqhi[i] = min(eqeq[i - 1], hieq[i - 1]) + 1;
                eqlo[i] = loeq[i - 1] + 1;
                if (a[i - 1] < a[i]) {
                    eqeq[i] = min(hieq[i - 1], eqeq[i - 1]);
                } else if (a[i - 1] == a[i]) {
                    eqeq[i] = 1000007;
                } else {
                    eqeq[i] = loeq[i - 1];
                }
            }
        }
        //cout << "( " << a[i] << " " << eqeq[i] << " " << eqhi[i] << " " << loeq[i] << " " << hieq[i] << " )\n";
    }
    auto lo = min(hilo[n], eqlo[n]);
    auto eq = min(loeq[n], min(eqeq[n], hieq[n]));
    auto hi = min(lohi[n], eqhi[n]);
    cout << min(lo, min(eq, hi)) << "\n";
}