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
#include <iostream>
using namespace std;
int ros[50005][2];
int mal[50005][2];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, prev, cur;
    cin >> n >> prev;
    ros[1][1] = 1;
    mal[1][1] = 1;
    for (int i = 2; i <= n; i++)
    {
        cin >> cur;
        ros[i][1] = min(mal[i-1][0], mal[i-1][1]) + 1;
        mal[i][1] = min(ros[i-1][0], ros[i-1][1]) + 1;
        ros[i][0] = mal[i-1][1];
        if (prev < cur && mal[i-1][0] < ros[i][0]) {
            ros[i][0] = mal[i-1][0];
        }
        mal[i][0] = ros[i-1][1];
        if (prev > cur && ros[i-1][0] < mal[i][0]){
            mal[i][0] = ros[i-1][0];
        }
        prev = cur;
    }
    int ans = min(mal[n][0], mal[n][1]);
    ans = min(ans, ros[n][0]);
    ans = min(ans, ros[n][1]);
    cout << ans;
    return 0;
}