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

#define ll long long

using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> A(n + 1);
    vector<pair<ll, ll>> B(n + 1, {0, 0}); // first - up ending, second - down ending
    for(ll i = 0; i < n; i++) cin >> A[i + 1];
    for(ll i = 2; i <= n; i++) {
        if(A[i - 1] < A[i]) {
            B[i].first = B[i - 1].second;
            B[i].second = B[i - 2].second + 1;
        } else if(A[i - 1] > A[i]) {
            B[i].second = B[i - 1].first;
            B[i].first = B[i - 2].first + 1;
        } else {
            B[i].first = B[i - 2].first + 1;
            B[i].second = B[i - 2].second + 1;
        }
    }
    cout << min(B[n].first, B[n].second) << "\n";
    return 0;
}