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
#include <iostream>
using namespace std;
const int M=5e4+9;
int tab[M];
int dp[M][4];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m=1000006,p0,p1,p2,p3;
    cin>>n;
    for(int i=2;i<=n+1;i++)cin>>tab[i];
    dp[2][0]=1;p0=m;
    dp[2][1]=1;p1=-m;
    dp[2][2]=0;p2=tab[2];
    dp[2][3]=0;p3=tab[2];
    for(int i=3;i<=n+1;i++)
    {
        if(i%2==1)
        {
            if(p0<=tab[i])
            {
                p0=-m;
                dp[i][0]=dp[i-1][0]+1;
            }else
            if(p0>tab[i])
            {
            p0=tab[i];
            dp[i][0]=dp[i-1][0];
            }
            if(p1>=tab[i])
            {
                p0=m;
                dp[i][1]=dp[i-1][1]+1;
            }else
            if(p1<tab[i])
            {
            p1=tab[i];
            dp[i][1]=dp[i-1][1];
            }
            if(p2<=tab[i])
            {
                p2=-m;
                dp[i][2]=dp[i-1][2]+1;
            }else
            if(p2>tab[i])
            {
            p2=tab[i];
            dp[i][2]=dp[i-1][2];
            }
            if(p3>=tab[i])
            {
                p3=m;
                dp[i][3]=dp[i-1][3]+1;
            }else
            if(p3<tab[i])
            {
            p3=tab[i];
            dp[i][3]=dp[i-1][3];
            }
        }
        else
        {
            if(p0>=tab[i])
            {
                p0=m;
                dp[i][0]=dp[i-1][0]+1;
            }else
            if(p0<tab[i])
            {
            p0=tab[i];
            dp[i][0]=dp[i-1][0];
            }
            if(p1<=tab[i])
            {
                p1=-m;
                dp[i][1]=dp[i-1][1]+1;
            }else
            if(p1>tab[i])
            {
            p1=tab[i];
            dp[i][1]=dp[i-1][1];
            }
            if(p2>=tab[i])
            {
                p2=m;
                dp[i][2]=dp[i-1][2]+1;
            }
            else
            if(p2<tab[i])
            {
            p2=tab[i];
            dp[i][2]=dp[i-1][2];
            }
            if(p3<=tab[i])
            {
                p3=-m;
                dp[i][3]=dp[i-1][3]+1;
            }
            else
            if(p3>tab[i])
            {
            p3=tab[i];
            dp[i][3]=dp[i-1][3];
            }
        }
    }
    cout<<min(dp[n+1][0],min(dp[n+1][1],min(dp[n+1][2],dp[n+1][3])));
}