@lkrabc

#include<bits/stdc++.h> using namespace std;int n,a[300005],dp[300005],top1,top2,stk1[300005],stk2[300005];int main(){scanf("%d",&n);for(int i = 1; i <= n; i++) scanf("%d",&a[i]);for(int i = 1; i <= n; i++){while(top1 && a[stk1[top1]] <= a[i]) top1--;stk1[++top1] = i;while(top2 && a[stk2[top2]] > a[i]) top2--;stk2[++top2] = i;dp[i]=dp[*lower_bound(stk2+1,stk2+top2+1,stk1[top1-1])-1] + 1;}printf("%d",dp[n]);return 0;}