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

#define pb push_back
#define fi first
#define sn second

typedef long long ll;
typedef vector<int> VI;
typedef vector<char> VC;
typedef pair<int, int> PI;

const int UNCHANGED = 0;
const int CHANGED = 1;

const int INC = 0;
const int DEC = 1;

int solve(VI &A, int n, int start) {
  VI D[2];
  D[UNCHANGED] = VI(n, 0);
  D[CHANGED] = VI(n, 0);

  D[CHANGED][0] = 1;

  int next = start;

  for (int i = 1; i < n; i++) {
    if (next == INC) {
      if (A[i] > A[i - 1]) {
        D[UNCHANGED][i] = min(D[UNCHANGED][i - 1], D[CHANGED][i - 1]);
        D[CHANGED][i] = min(D[UNCHANGED][i - 1], D[CHANGED][i - 1]) + 1;
      } else {
        D[UNCHANGED][i] = D[CHANGED][i - 1];
        D[CHANGED][i] = min(D[UNCHANGED][i - 1], D[CHANGED][i - 1]) + 1;
      }
    } else {
      if (A[i] < A[i - 1]) {
        D[UNCHANGED][i] = min(D[UNCHANGED][i - 1], D[CHANGED][i - 1]);
        D[CHANGED][i] = min(D[UNCHANGED][i - 1], D[CHANGED][i - 1]) + 1;
      } else {
        D[UNCHANGED][i] = D[CHANGED][i - 1];
        D[CHANGED][i] = min(D[UNCHANGED][i - 1], D[CHANGED][i - 1]) + 1;
      }
    }

    next++;
    next %= 2;
  }

//   for (int i = 1; i < n; i++) {
// 	cout<<D[UNCHANGED][i]<<" ";
//   }
//   cout<<endl;
//   for (int i = 1; i < n; i++) {
// 	cout<<D[CHANGED][i]<<" ";
//   }
//   cout<<endl;
//   cout<<endl;


  return min(D[UNCHANGED][n - 1], D[CHANGED][n - 1]);
}

int main() {
  int n;
  cin >> n;

  VI A(n);

  for (int i = 0; i < n; i++) {
    cin >> A[i];
  }

  cout << min(solve(A, n, INC), solve(A, n, DEC)) << endl;

  return 0;
}