func_code_string: #include <bits/stdc++.h>   using namespace std;   mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());   const int N = 3e5;   int n, a[N + 1], b[N + 1], c[N + 1];   int dp[N + 1];   vector<int> g1[N + 1], g2[N + 1];   signed main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     cin >> n;     for (int i = 1; i <= n; ++i) {       cin >> a[i];     }     vector<pair<int, int> > st;     for (int i = 1; i <= n; ++i) {       while (!st.empty() && st.back().first < a[i]) {         st.pop_back();       }       if (!st.empty()) {         b[i] = st.back().second;       }       st.emplace_back(a[i], i);     }     st.clear();     for (int i = 1; i <= n; ++i) {       while (!st.empty() && st.back().first > a[i]) {         st.pop_back();       }       if (!st.empty()) {         c[i] = st.back().second;       }       st.emplace_back(a[i], i);     }     st.clear();     for (int i = n; i >= 1; --i) {       while (!st.empty() && st.back().first < a[i]) {         st.pop_back();       }       if (!st.empty()) {         g1[st.back().second].emplace_back(i);       }       st.emplace_back(a[i], i);     }     st.clear();     for (int i = n; i >= 1; --i) {       while (!st.empty() && st.back().first > a[i]) {         st.pop_back();       }       if (!st.empty()) {         g2[st.back().second].emplace_back(i);       }       st.emplace_back(a[i], i);     }     dp[1] = 0;     for (int i = 2; i <= n; ++i) {       dp[i] = dp[i - 1] + 1;       if (b[i]) dp[i] = min(dp[i], dp[b[i]] + 1);       if (c[i]) dp[i] = min(dp[i], dp[c[i]] + 1);       for (int x : g1[i]) {         if (x >= b[i]) {           dp[i] = min(dp[i], dp[x] + 1);         }       }       for (int x : g2[i]) {         if (x >= c[i]) {           dp[i] = min(dp[i], dp[x] + 1);         }       }     }     cout << dp[n] <<   n ;     return 0;   }   