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

typedef long long int lli;

using namespace std;

#define MAX4 10010
#define MAX5 100010
#define MAX6 1000010

template <typename T >
void dbg(T last)
{
  cout << last << "\n";
}

template <typename T, typename ...args>
void dbg(T current, args ...next)
{
  cout << current << ' ';
  dbg(next...);
}

//-----------------------------------------------------------------------------------------------//
int tab[MAX5];
int dp[MAX5][2];

bool myGreater(int x, int y)
{
  return x < y;
}

bool mySmaller(int x, int y)
{
  return x > y;
}

int calculateDP(bool (*check1)(int, int), bool (*check2)(int, int), int n)
{
  for (int i=0;i<=n;i++)
  {
    dp[i][0] = 0;
    dp[i][1] = 0;
  }

  for (int i=1;i<=n;i++)
  {
    if ((i%2 == 1 && check1(tab[i], tab[i-1])) || (i%2 == 0 && check2(tab[i], tab[i-1])))
    {
      dp[i][0] = min(dp[i-1][0], dp[i-1][1]);
      dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1;
    }
    else
    {
      dp[i][0] = dp[i-1][1];
      dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1;
    }
  }

  return min(dp[n][0], dp[n][1]);
}

void solve()
{
  int n;
  cin >> n;

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

  tab[0] = INT_MAX;
  int minn = calculateDP(mySmaller, myGreater, n);
  tab[0] = INT_MIN;
  minn = min(minn, calculateDP(myGreater, mySmaller, n));
  cout << minn << "\n";
}

int main()
{
  std::ios::sync_with_stdio(false);

  solve();

  return 0;
}