problem

Given the sequence $ A $ of length $ N $. The $ i $ item in $ A $ is $ A_i $. You can do the following for this sequence:

* $ 1 \ leq i \ leq N --Choose the integer i that is 1 $. Swap the value of $ A_i $ with the value of $ A_ {i + 1} $.



Find the minimum number of operations required to make $ A $ a sequence of bumps.

A sequence of length $ N $ that satisfies the following conditions is defined as a sequence of irregularities.

* For any $ i $ that satisfies $ 1 <i <N $, ​​$ A_ {i + 1}, A_ {i --1}> A_i $ or $ A_ {i + 1}, A_ {i --1} <A_i Satisfy $.
Intuitively, increase, decrease, increase ... (decrease, like $ 1, \ 10, \ 2, \ 30, \ \ dots (10, \ 1, \ 30, \ 2, \ \ dots) $ It is a sequence that repeats increase, decrease ...).



output

Output the minimum number of operations required to make a sequence of bumps. Also, output a line break at the end.

Example

Input

5
1 2 3 4 5


Output

2
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> a;

int solve(int x, int now);

int main() {
  cin >> n;
  for(int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    a.push_back(x);
  }
  cout << min(solve(0, 1), solve(1, 1)) << endl;
  return 0;
}

int solve(int x, int now) {
  int ans = 0;
  while(now < a.size() &&
        (a[now - 1] < a[now]) == (now + x) % 2)
    ++now;
  if(now == a.size()) return 0;
  swap(a[now], a[now - 1]);
  ans = solve(x, now + 1);
  swap(a[now], a[now - 1]);
  if(now + 1 < a.size() &&
     (a[now] < a[now + 1]) != (now + 1 + x) % 2 &&
     (a[now - 1] < a[now + 1]) == (now + x) % 2) {
    swap(a[now], a[now + 1]);
    ans = min(ans, solve(x, now + 1));
    swap(a[now], a[now + 1]);
  }
  return ans + 1;
}
