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

using namespace std;

const int MAX =  1000000000;
const int MIN = -1000000000;

int calc_min(const vector<int>& sounds, bool greater_at_0, bool start_with_change)
{
    int changes = 0;
    // i==0
    int at_i_minus_1 = 0;
    int at_i = sounds[0];
    bool greater_at_i = greater_at_0;
    if(start_with_change)
    {
        ++changes;
        at_i = (greater_at_0 ? MAX : MIN);
    }
    
    // i==1
    for(int i=1; i<sounds.size(); ++i)
    {
        at_i_minus_1 = at_i;
        at_i = sounds[i];
        greater_at_i = !greater_at_i;
        
        if(greater_at_i)
        {
            if(at_i<=at_i_minus_1)
            {
                at_i = MAX;
                ++changes;
            }
        }
        else
        {
            if(at_i>=at_i_minus_1)
            {
                at_i = MIN;
                ++changes;
            }
        }
    }
    return changes;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int n;
    cin >> n;
    vector<int> sounds(n,0);
    for(int i=0; i<n; ++i)
    {
        cin >> sounds[i];
    }
    
    int changes =           calc_min(sounds, false, false);
    changes = min( changes, calc_min(sounds, false, true) );
    changes = min( changes, calc_min(sounds, true,  false));
    changes = min( changes, calc_min(sounds, true,  true) );
    cout << changes;
    
    return 0;
}