There are n beautiful skyscrapers in New York, the height of the i-th one is h_i. Today some villains have set on fire first n - 1 of them, and now the only safety building is n-th skyscraper.

Let's call a jump from i-th skyscraper to j-th (i < j) discrete, if all skyscrapers between are strictly lower or higher than both of them. Formally, jump is discrete, if i < j and one of the following conditions satisfied: 

  * i + 1 = j 
  * max(h_{i + 1}, …, h_{j - 1}) < min(h_i, h_j) 
  * max(h_i, h_j) < min(h_{i + 1}, …, h_{j - 1}). 



At the moment, Vasya is staying on the first skyscraper and wants to live a little longer, so his goal is to reach n-th skyscraper with minimal count of discrete jumps. Help him with calcualting this number.

Input

The first line contains a single integer n (2 ≤ n ≤ 3 ⋅ 10^5) — total amount of skyscrapers.

The second line contains n integers h_1, h_2, …, h_n (1 ≤ h_i ≤ 10^9) — heights of skyscrapers.

Output

Print single number k — minimal amount of discrete jumps. We can show that an answer always exists.

Examples

Input


5
1 3 1 4 5


Output


3

Input


4
4 2 2 4


Output


1

Input


2
1 1


Output


1

Input


5
100 1 100 1 100


Output


2

Note

In the first testcase, Vasya can jump in the following way: 1 → 2 → 4 → 5.

In the second and third testcases, we can reach last skyscraper in one jump.

Sequence of jumps in the fourth testcase: 1 → 3 → 5.
#include <bits/stdc++.h>
using namespace std;
long long INF = 1LL << 60;
long long MOD = 1e9 + 7;
namespace output {
void pr(short x) { cout << x; }
void pr(signed x) { cout << x; }
void pr(long x) { cout << x; }
void pr(long long x) { cout << x; }
void pr(unsigned short x) { cout << x; }
void pr(unsigned x) { cout << x; }
void pr(unsigned long x) { cout << x; }
void pr(unsigned long long x) { cout << x; }
void pr(float x) { cout << x; }
void pr(double x) { cout << x; }
void pr(long double x) { cout << x; }
void pr(char x) { cout << x; }
void pr(const char *x) { cout << x; }
void pr(const string &x) { cout << x; }
void pr(bool x) { cout << x; }
template <size_t sz>
void pr(const bitset<sz> &x) {
  cout << x;
}
template <class T>
void pr(const complex<T> &x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2> &x);
template <class T1, class T2, class T3>
void pr(const tuple<T1, T2, T3> &x);
template <class T>
void pr(const T &x);
template <class T, class... Ts>
void pr(const T &t, const Ts &...ts) {
  pr(t);
  pr(ts...);
}
template <class T1, class T2>
void pr(const pair<T1, T2> &x) {
  pr("(", x.first, ", ", x.second, ")");
}
template <class T1, class T2, class T3>
void pr(const tuple<T1, T2, T3> &x) {
  pr("(", get<0>(x), ", ", get<1>(x), ", ", get<2>(x), ")");
}
template <class T>
void pr(const T &x) {
  pr("[");
  bool fst = 1;
  for (const auto &a : x) pr(!fst ? ", " : "", a), fst = 0;
  pr("]");
}
void print() { pr("\n"); }
template <class T, class... Ts>
void print(const T &t, const Ts &...ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  print(ts...);
}
}  // namespace output
using namespace output;
template <class T1, class T2>
istream &operator>>(istream &is, pair<T1, T2> &x) {
  is >> x.first >> x.second;
  return is;
}
template <class T1, class T2, class T3>
istream &operator>>(istream &is, tuple<T1, T2, T3> &x) {
  is >> get<0>(x) >> get<1>(x) >> get<2>(x);
  return is;
}
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &x : v) is >> x;
  return is;
}
long long powa(long long base, long long exp) {
  long long res = 1;
  while (exp) {
    if (exp & 1) res = res * base % MOD;
    base = base * base % MOD;
    exp >>= 1;
  }
  return res;
}
bool mini(long long &a, long long b) { return b < a ? a = b, 1 : 0; }
bool maxi(long long &a, long long b) { return b > a ? a = b, 1 : 0; }
signed main() {
  ios::sync_with_stdio(0), cin.tie(0);
  long long n;
  cin >> n;
  vector<long long> a(n);
  set<long long> raw;
  map<long long, long long> trans;
  for (long long i = (0); i < (n); ++i) {
    cin >> a[i];
    raw.insert(a[i]);
  }
  long long m = 0;
  for (long long i : raw) {
    trans[i] = m;
    ++m;
  }
  for (long long i = (0); i < (n); ++i) {
    a[i] = trans[a[i]];
  }
  vector<long long> tree(2 * m);
  auto upd = [&](long long x, long long delta) {
    x += m;
    tree[x] = delta;
    x /= 2;
    while (x) {
      tree[x] = max(tree[2 * x], tree[2 * x + 1]);
      x /= 2;
    }
  };
  auto query = [&](long long l, long long r) {
    l += m;
    r += m;
    long long res = 0;
    while (l <= r) {
      if (l & 1) maxi(res, tree[l++]);
      if (!(r & 1)) maxi(res, tree[r--]);
      l /= 2;
      r /= 2;
    }
    return res;
  };
  vector<long long> nextlt(n), nextgt(n);
  for (long long i = (0); i < (n); ++i) {
    nextlt[i] = query(0, a[i]);
    nextgt[i] = query(a[i], m - 1);
    upd(a[i], i);
  }
  vector<long long> dp(n, INF);
  dp[0] = 0;
  vector<long long> bigdptree(2 * n, INF), smaldptree(2 * n, INF);
  auto dpupd = [&](vector<long long> &tree, long long x, long long val) {
    x += n;
    tree[x] = val;
    x /= 2;
    while (x) {
      tree[x] = min(tree[2 * x], tree[2 * x + 1]);
      x /= 2;
    }
  };
  auto dpquery = [&](vector<long long> &tree, long long l, long long r) {
    l += n;
    r += n;
    long long res = INF;
    while (l <= r) {
      if (l & 1) mini(res, tree[l++]);
      if (!(r & 1)) mini(res, tree[r--]);
      l /= 2;
      r /= 2;
    }
    return res;
  };
  vector<pair<long long, long long> > bigsuf, smalsuf;
  for (long long i = (0); i < (n); ++i) {
    if (i) {
      if (a[i - 1] < a[i]) {
        dp[i] = 1 + dpquery(bigdptree, nextgt[i], n - 1);
      } else if (a[i - 1] > a[i]) {
        dp[i] = 1 + dpquery(smaldptree, nextlt[i], n - 1);
      } else {
        dp[i] = 1 + dp[i - 1];
      }
    }
    mini(dp[i], 1 + dp[i - 1]);
    while (!bigsuf.empty() && bigsuf.back().second <= a[i]) {
      dpupd(bigdptree, bigsuf.back().first, INF);
      bigsuf.pop_back();
    }
    bigsuf.emplace_back(i, a[i]);
    dpupd(bigdptree, i, dp[i]);
    while (!smalsuf.empty() && smalsuf.back().second >= a[i]) {
      dpupd(smaldptree, smalsuf.back().first, INF);
      smalsuf.pop_back();
    }
    smalsuf.emplace_back(i, a[i]);
    dpupd(smaldptree, i, dp[i]);
  }
  print(dp.back());
}
