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 <iostream>
#include <vector>
using namespace std;

const int DOWN = 0;
const int UP = 1;

int main() {
    int N; cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    vector<long long> nA = A;

    int res = 1<<29;
    for (int iter = 0; iter < 2; ++iter) {
        A = nA;
        int cur = DOWN;
        if (iter == 1) cur = UP;
        int con = 0;
        for (int i = 0; i + 1 < N; ++i) {
            if (cur == DOWN) {
                if (A[i] < A[i+1]) {
                    if (i + 2 < N && A[i+1] > A[i+2] && A[i] > A[i+2]) {
                        ++con;
                        ++i;
                        swap(A[i], A[i+1]);
                        cur = 1 - cur;
                        //cout << iter << ", " << i << ";; " << A[i] << ", " << A[i+1] << endl;
                    }
                    else {
                        ++con;
                        swap(A[i], A[i+1]);
                        //cout << iter << ", " << i << ";; " << A[i] << ", " << A[i+1] << endl;
                    }
                }
            }
            else {
                if (A[i] > A[i+1]) {
                    if (i + 2 < N && A[i+1] < A[i+2] && A[i] < A[i+2]) {
                        ++con;
                        ++i;
                        swap(A[i], A[i+1]);
                        cur = 1 - cur;
                        //cout << iter << ", " << i << ";; " << A[i] << ", " << A[i+1] << endl;
                    }
                    else {
                        ++con;
                        swap(A[i], A[i+1]);
                        //cout << iter << ", " << i << ";; " << A[i] << ", " << A[i+1] << endl;
                    }
                }
            }
            cur = 1 - cur;
        }
        res = min(res, con);
    }
    cout << res << endl;
}

