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

#define MAX_N 100000
#define BAD 1000000

using namespace std;

int n;
int sound[MAX_N];
int up[MAX_N];
int changedUp[MAX_N];
int down[MAX_N];
int changedDown[MAX_N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &sound[i]);
    }

    up[0] = 0;
    down[0] = 0;
    changedUp[0] = 1;
    changedDown[0] = 1;

    for (int i = 1; i < n; i++) {
        changedUp[i] = min(down[i - 1], changedDown[i - 1]) + 1;
        changedDown[i] = min(up[i - 1], changedUp[i - 1]) + 1;
        up[i] = min(changedDown[i - 1], sound[i] > sound[i - 1] ? down[i - 1] : BAD);
        down[i] = min(changedUp[i - 1], sound[i] < sound[i - 1] ? up[i - 1] : BAD);
    }

    printf("%d\n", min(
        min(up[n - 1], changedUp[n - 1]),
        min(down[n - 1], changedDown[n - 1])));
}