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
// Author: Bartek Knapik

#include <cstdio>

const int INF = 1000000000;

int N;
int mem[50009][2];
int a[50009];

inline int my_min(int& a, int& b) { return a < b ? a : b; }

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

    mem[1][0] = mem[1][1] = 0;
    mem[2][0] = a[0] > a[1] ? 0 : 1;
    mem[2][1] = a[0] < a[1] ? 0 : 1;

    for (int k = 2; k < N; ++k)
    {
        mem[k + 1][0] = mem[k][1] + ((mem[k][1] == mem[k - 1][0] ? a[k - 1] : INF) > a[k] ? 0 : 1);
        mem[k + 1][1] = mem[k][0] + ((mem[k][0] == mem[k - 1][1] ? a[k - 1] : -INF) < a[k] ? 0 : 1);
    }

    printf("%d\n", my_min(mem[N][0], mem[N][1]));

    return 0;
}