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
#include <cstdio>
#include <climits>
#include <algorithm>

using namespace std;

const int MAXN = 50000;

const int ZMI = 1;
const int NIE = 0;

const int NIEMOZLIWE = INT_MAX;

int N;
int dzwieki[MAXN + 5];
int t1[MAXN + 5][2];
int t2[MAXN + 5][2];

void incCheck(int *v) {
    if (*v != NIEMOZLIWE) {
        *v += 1;
    }
}

void dyn(int t[][2], int i, int kierunek) {
    t[i][ZMI] = min(t[i-1][ZMI],t[i-1][NIE]);
    incCheck(&t[i][ZMI]);
    if (
        (kierunek && dzwieki[i] > dzwieki[i-1]) ||
        (!kierunek && dzwieki[i] < dzwieki[i-1])
        ) {
        t[i][NIE] = min(t[i-1][ZMI],t[i-1][NIE]);
    } else {
        t[i][NIE] = t[i-1][ZMI];
    }
}

#undef DEBUGPRINT

int main() {
    scanf("%d", &N);
    for (int i =0; i< N; ++i) {
        scanf("%d", dzwieki+i);
    }
    t1[0][ZMI] = t2[0][ZMI] = 1;
    t1[0][NIE] = t2[0][NIE] = 0;
    int kierunek = 0;
    for (int i = 1; i < N; ++i) {
        dyn(t1, i, kierunek);
        kierunek = !kierunek;
        dyn(t2, i, kierunek);
    }
#ifdef DEBUGPRINT
    for (int i =0; i< N; ++i) {
        printf("%d", dzwieki[i]);
    }
    putchar('\n');
    for (int i =0; i< N; ++i) {
        printf("%d", t1[i][ZMI]);
    }
    putchar('\n');
    for (int i =0; i< N; ++i) {
        printf("%d", t1[i][NIE]);
    }
    putchar('\n');
    putchar('\n');
    for (int i =0; i< N; ++i) {
        printf("%d", t2[i][ZMI]);
    }
    putchar('\n');
    for (int i =0; i< N; ++i) {
        printf("%d", t2[i][NIE]);
    }
    putchar('\n');
#endif
    printf("%d", min(min(t1[N-1][ZMI],t1[N-1][NIE]), min(t2[N-1][ZMI],t2[N-1][NIE])));
}