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

using namespace std;

int n;
vector<int> tab;

int licz(vector<int> V){
    
    vector<int> dp[3];
    for(int i=0; i<3; i++)dp[i].resize(n);
    dp[0][0] = 0;//niezmieniam
    dp[1][0] = 1;//daje nanajmniejsze
    dp[2][0] = 1;//daje najwieksze
    
    for(int i=1; i<n; i++){
        if(i%2==1){ //pierwszy jest maly 
            if(tab[i-1] < tab[i]){
                dp[0][i] = min( dp[0][i-1], min( dp[1][i-1], dp[2][i-1] ) );
            }else{
                dp[0][i] = dp[1][i-1];
            }
            dp[1][i] = dp[1][i-1] + 1;
            dp[2][i] = min( dp[0][i-1], min( dp[1][i-1], dp[2][i-1] ) ) + 1;
        }
        if(i%2==0){
            if(tab[i-1] > tab[i]){
                dp[0][i] = min( dp[0][i-1], min( dp[1][i-1], dp[2][i-1] ) );
            }else{
                dp[0][i] = dp[2][i-1];
            }
            dp[2][i] = dp[2][i-1] + 1;
            dp[1][i] = min( dp[0][i-1], min( dp[1][i-1], dp[2][i-1] ) ) + 1;
        }
    }
    /*for(int i=0; i<n; i++){
        for(int j=0; j<3; j++)cout<<dp[j][i]<<" ";
        cout<<endl;
    }*/
    return min(dp[0][n-1], min( dp[1][n-1], dp[2][n-1] ) );
}

int main(){
    cin>>n;
    tab.resize(n);
    for(auto &x : tab)cin>>x;
    int wynik  = licz(tab);
    for(auto &x : tab)x = 2e6 - x;
    cout<<min( wynik, licz(tab));
}