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 MOD = 1e9 + 7;
const long long INF = 1e18;
const double E = 1e-18;
const double PI = acos(-1);
mt19937_64 rnd(time(0));
long long p1 = 31, p2 = 37, p3 = 7, p4 = rnd() % 100 + 1, md1 = MOD,
          md2 = 998244353, md3 = 998244357, md4 = rnd() % 1000000000;
long long n, m, k, T, a[300001], dp[300001];
pair<long long, long long> b[300001];
bool tt[300001];
long long binpow(long long h, long long r, long long md = MOD) {
  long long l = 1;
  while (r) {
    if (r & 1) l *= h, l %= md;
    h *= h;
    h %= md;
    r /= 2;
  }
  return l;
}
long long gcd(long long x, long long y) {
  if (x == 0 || y == 0) return x + y;
  if (x < y) swap(x, y);
  while (x && y) {
    x %= y;
    swap(x, y);
  }
  return x + y;
}
struct sparse_table_1 {
  long long d[300001][20];
  void build(int n) {
    for (int i = n; i > 0; i--) {
      d[i][0] = a[i];
      for (int j = 1, u = 2; j < 20; j++, u *= 2) {
        if (i + u - 1 > n) break;
        d[i][j] = min(d[i][j - 1], d[i + u / 2][j - 1]);
      }
    }
  }
  long long get(int x, int y) {
    return min(d[x][b[y - x + 1].second],
               d[y - b[y - x + 1].first + 1][b[y - x + 1].second]);
  }
};
struct sparse_table_2 {
  long long d[300001][20];
  void build(int n) {
    for (int i = n; i > 0; i--) {
      d[i][0] = a[i];
      for (int j = 1, u = 2; j < 20; j++, u *= 2) {
        if (i + u - 1 > n) break;
        d[i][j] = max(d[i][j - 1], d[i + u / 2][j - 1]);
      }
    }
  }
  long long get(int x, int y) {
    return max(d[x][b[y - x + 1].second],
               d[y - b[y - x + 1].first + 1][b[y - x + 1].second]);
  }
};
sparse_table_1 g1;
sparse_table_2 g2;
struct segment_tree {
  long long d[2000001];
  void build(int h, int l, int r) {
    if (l == r) {
      d[h] = 1e18;
      return;
    }
    int w = (l + r) / 2;
    build(h * 2, l, w);
    build(h * 2 + 1, w + 1, r);
    d[h] = 1e18;
  }
  void update(int h, int l, int r, int x, long long k) {
    if (l == r) {
      d[h] = k;
      return;
    }
    int w = (l + r) / 2;
    if (x <= w)
      update(h * 2, l, w, x, k);
    else
      update(h * 2 + 1, w + 1, r, x, k);
    d[h] = min(d[h * 2], d[h * 2 + 1]);
  }
  long long get(int h, int l, int r, int x, int y) {
    if (x > y) return 1e18;
    if (l == x && y == r) {
      return d[h];
    }
    int w = (l + r) / 2;
    return min(get(h * 2, l, w, x, min(y, w)),
               get(h * 2 + 1, w + 1, r, max(x, w + 1), y));
  }
};
segment_tree q1, q2;
void solve() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  g1.build(n);
  g2.build(n);
  q1.build(1, 1, n);
  q2.build(1, 1, n);
  dp[1] = 0;
  set<pair<int, int> > s1, s2;
  s1.insert(make_pair(a[1], 1));
  s2.insert(make_pair(a[1], 1));
  q1.update(1, 1, n, 1, 0);
  q2.update(1, 1, n, 1, 0);
  for (int i = 2; i <= n; i++) {
    long long o = 1e18;
    long long l = 1, r = i;
    while (l < r) {
      int w = (l + r) / 2;
      if (g1.get(w, i - 1) <= a[i])
        l = w + 1;
      else
        r = w;
    }
    o = min(o, q1.get(1, 1, n, max(l - 1, 1ll), i) + 1);
    l = 1, r = i;
    while (l < r) {
      int w = (l + r) / 2;
      if (g2.get(w, i - 1) >= a[i])
        l = w + 1;
      else
        r = w;
    }
    o = min(o, q2.get(1, 1, n, max(l - 1, 1ll), i) + 1);
    dp[i] = o;
    while (s1.size()) {
      auto u = s1.end();
      u--;
      if ((*u).first >= a[i]) {
        q1.update(1, 1, n, (*u).second, 1e18);
        s1.erase(u);
      } else
        break;
    }
    while (s2.size()) {
      if ((*s2.begin()).first <= a[i]) {
        q2.update(1, 1, n, (*s2.begin()).second, 1e18);
        s2.erase(s2.begin());
      } else
        break;
    }
    s1.insert(make_pair(a[i], i));
    s2.insert(make_pair(a[i], i));
    q1.update(1, 1, n, i, dp[i]);
    q2.update(1, 1, n, i, dp[i]);
  }
  cout << dp[n] << "\n";
}
int main() {
  long long o = 0, u = -1;
  for (int i = 1; i <= 3e5; i++) {
    if (i / 2 == o) o = i, u++;
    b[i] = make_pair(o, u);
  }
  long long t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
