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
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <math.h>
#include <stdio.h>
#include <deque>
#include <unordered_map>
#include <cassert>
#include <numeric>
#include <queue>

#include <string>
#include <stack>

#define LL long long

using namespace std;

bool alternate(int a, int b, int c)
{
    if (a < b && b > c) return true;
    if (a > b && b < c) return true;
    return false;
}

int toState(int x, int y)
{
    return x * 3 + y;
}

pair<int,int> fromState(int state) {
    return make_pair(state/3, state%3);
}

const int SAME = 0;
const int MIN = 1;
const int MAX = 2;

const int MIN_VAL = -10000000;
const int MAX_VAL = 10000000;

int deref(int aRef, int val)
{
    if (aRef == SAME) return val;
    if (aRef == MIN) return MIN_VAL;
    if (aRef == MAX) return MAX_VAL;
    assert(false);
    return -1;
}

LL solve(vector<int> &v) {
    const int n = v.size();
    const LL INF = 99999999;

    vector<vector<int> > dp(9, vector<int>(n+1));

    for (int state=0; state < 9; state++)
    {
        pair<int, int> p = fromState(state);
        int x = p.first;
        int y = p.second;
        dp[state][0] = (x>0? 1 : 0);
        dp[state][1] = (x>0 ? 1 : 0) + ((y>0) ? 1 : 0);
    }
    
    for (int i=2; i < n; i++)
    {
        for (int state=0; state < 9; state++)
        {
            dp[state][i] = INF;
            pair<int, int> current = fromState(state);
            for (int halfState=0; halfState < 3; halfState++) {
               pair<int, int> prev = {current.second, halfState};
               int prevState = toState(prev.first, prev.second);
               
               if (current.second != prev.first) continue;
               int diff = (current.first > 0) ? 1 : 0;
               if (alternate(
                    deref(current.first, v[i]),
                    deref(current.second, v[i-1]),
                    deref(prev.second, v[i-2]))) {

                    int res = dp[prevState][i-1]  + diff;
                    if (res < dp[state][i]) {
                        dp[state][i] = res;
                    }   
                }
            }
            //cerr << "i=" << i << ",dp[" << state << "]=" << dp[state][i] << ",";
        }
        //cerr << "\n";
    }
    LL changes = INF;
    for (int state=0; state < 9; state++)
    {
        changes = min((int)changes, dp[state][n-1]);
    }

    return changes;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> v;
    for (int i=0; i < n; i++) {
        int x; cin >> x;
        v.emplace_back(x);
    }
    LL res = solve(v);
    cout << res << "\n";
}