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
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    int tab[n];
    for(int k=0;k<n;k++)
        cin >> tab[k];
    vector<int> dp[4];
    /// 0 smaller, 1 greater - without changes
    /// 2 small change, 3 great change
    for(int k=0;k<4;k++)
        dp[k].resize(n,INT_MAX);
    dp[0][n-1] = dp[1][n-1] = 0;
    dp[2][n-1] = dp[3][n-1] =  1;
    for(int i=n-2;i>=0;i--) {
        dp[2][i] = min(dp[1][i+1],dp[3][i+1]) + 1;
        dp[3][i] = min(dp[0][i+1],dp[2][i+1]) + 1;
        dp[0][i] = dp[3][i+1];
        dp[1][i] = dp[2][i+1];
        if(tab[i] < tab[i+1]) {
            dp[0][i] = min(dp[1][i+1],dp[3][i+1]);
        }
        if(tab[i] > tab[i+1]) {
            dp[1][i] = min(dp[0][i+1],dp[2][i+1]);
        }
        //cout << i << " " << dp[0][i] << " " << dp[1][i] << " " << dp[2][i] <<endl;
    }
    cout << min(dp[0][0],min(dp[1][0],min(dp[2][0],dp[3][0]))) <<endl;
}