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
#include <iostream>
#include <fstream>

using namespace std;

int n;
int *a;
int *dp[4];


int main()
{
    scanf("%d", &n);
    a=new int[n];
    dp[0]=new int[n];
    dp[1]=new int[n];
    dp[2]=new int[n];
    dp[3]=new int[n];
    for(int i=0; i<n; i++){
        scanf("%d", a+i);
        dp[0][i]=0;
        dp[1][i]=0;
        dp[2][i]=0;
        dp[3][i]=0;
    }
    //int minfty, infty;
    dp[0][0]=1;///gora nieskonczonosc
    dp[1][0]=0;///gora bez ruchu
    dp[2][0]=0;///dol bez ruchu
    dp[3][0]=1;///dol nieskonczonosc
    for(int i=1;i<n; i++){
        ///rozwazyc infty/minfty
        //if(infty>a[i-1])
            dp[0][i]=min(dp[2][i-1], dp[3][i-1])+1;
        //else
        //    dp[0][i] = dp[3][i-1]+1;
        //if(minfty<a[i-1])
            dp[3][i]=min(dp[0][i-1], dp[1][i-1])+1;
        //else
        //    dp[3][i] = dp[0][i-1]+1;
        if(a[i]>a[i-1])
            dp[1][i]=min(dp[2][i-1], dp[3][i-1]);
        else //if(a[i]>minfty)
            dp[1][i]=dp[3][i-1];
        if(a[i]<a[i-1])
            dp[2][i]=min(dp[0][i-1], dp[1][i-1]);
        else //if(a[i]<infty)
            dp[2][i]=dp[0][i-1];
    }
    printf("%d", min(min(dp[0][n-1], dp[1][n-1]), min(dp[2][n-1], dp[3][n-1])));
    return 0;
}