func_code_string: #include <bits/stdc++.h>   using namespace std;   int dx[] = {0, 0, 1, -1};   int dy[] = {1, -1, 0, 0};   int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};   int dy8[] = {1, -1, -1, 0, 1, -1, 0, 1};   int kx8[] = {1, 1, 2, 2, -1, -1, -2, -2};   int ky8[] = {2, -2, 1, -1, 2, -2, 1, -1};   long long poww(long long a, long long b) {     if (b == 0) return 1;     long long x = poww(a, b / 2);     x = x * x;     if (b % 2 == 1) x = x * a;     return x;   }   long long bigmod(long long a, long long b, long long c) {     if (b == 0) return 1 % c;     long long x = bigmod(a, b / 2, c);     x = x * x % c;     if (b % 2 == 1) x = x * a % c;     return x;   }   long long mod_inverse(long long a, long long mod) {     return bigmod(a, mod - 2, mod);   }   int a[100005 * 3], sp[20][100005 * 3], lg[100005 * 3], n;   int spp[20][100005 * 3];   void logcal() {     int cnt = 0;     int p = 2;     while (p <= 300000) {       lg[p] = 1;       p *= 2;     }     for (int i = 0; i <= 300000; i++) {       if (lg[i]) {         cnt++;       }       lg[i] = cnt;     }   }   long long query1(int l, int r) {     int ln = lg[r - l + 1];     int k = 1 << ln;     int df = r - l + 1 - k;     return (min(sp[ln][l], sp[ln][l + df]));   }   long long query2(int l, int r) {     int ln = lg[r - l + 1];     int k = 1 << ln;     int df = r - l + 1 - k;     return (max(spp[ln][l], spp[ln][l + df]));   }   long long dp[100005 * 3];   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     logcal();     cin >> n;     for (int i = 1; i <= n; i++) {       cin >> a[i];     }     for (int i = 1; i <= n; i++) {       sp[0][i] = a[i];       spp[0][i] = a[i];     }     for (int i = 1; 1 << i <= n; i++) {       for (int j = 1; j + (1 << i) <= n + 1; j++) {         sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);         spp[i][j] = max(spp[i - 1][j], spp[i - 1][j + (1 << (i - 1))]);       }     }     for (int i = 1; i <= n; i++) dp[i] = 2134567891;     int N = n;     for (int i = 1; i <= N; i++) {       dp[i] = min(dp[i - 1] + 1, dp[i]);       int lw = 1, hi = i - 1, ans = 0, mid;       while (lw <= hi) {         int mid = (lw + hi) / 2;         int mx = query2(mid, i - 1);         if (mx >= a[i]) {           lw = mid + 1;           ans = mid;         } else {           hi = mid - 1;         }       }       if (ans > 0) {         dp[i] = min(dp[ans] + 1, dp[i]);       }       lw = i + 1, hi = n, ans = 0, mid;       while (lw <= hi) {         int mid = (lw + hi) / 2;         int mx = query2(i + 1, mid);         if (mx >= a[i]) {           ans = mid;           hi = mid - 1;         } else {           lw = mid + 1;         }       }       if (ans <= n && ans > 0) {         dp[ans] = min(dp[ans], dp[i] + 1);       }       lw = 1, hi = i - 1, ans = 0, mid;       while (lw <= hi) {         int mid = (lw + hi) / 2;         int mn = query1(mid, i - 1);         if (mn > a[i]) {           hi = mid - 1;         } else {           lw = mid + 1;           ans = mid;         }       }       if (ans > 0) {         dp[i] = min(dp[ans] + 1, dp[i]);       }       lw = i + 1, hi = n, ans = 0, mid;       while (lw <= hi) {         int mid = (lw + hi) / 2;         int mn = query1(i + 1, mid);         if (mn > a[i]) {           lw = mid + 1;         } else {           hi = mid - 1;           ans = mid;         }       }       if (ans <= n && ans > 0) {         dp[ans] = min(dp[ans], dp[i] + 1);       }     }     cout << dp[n] - 1 << endl;     return 0;   }   