代码，理论$O(n)$，但只 $\color{green}{\text{AC}}$了6个点，其余$\color{green}{\text{WA}}$了

大佬救命

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[300007];
struct pd{
    int mxn,mnn;
    pd(){mxn=mnn=0;}
};
pd k[300007];
struct _stack_{
    int a[1000007],n;
    _stack_(){n=0;}
    void push(int x){a[++n]=x;return;}
    void pop(){--n;return;}
    void clear(){n=0;}
    bool empty(){return (n==0);};
    int size(){return n;}
    int top(){return a[n];}
};
int dfs(int x,bool is_mx){
	if(is_mx){
	    if(x<=k[k[x].mnn].mxn)
	        return (x-k[x].mnn+1);
	    return dfs(k[x].mnn,0);
	}
	else{
	    if(x>=k[k[x].mxn].mnn)
	        return (k[x].mxn-x+1);
	    return dfs(k[x].mxn,1);
	}
} 
_stack_ mxn,mnn;
int ans;
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	    scanf("%lld",a+i);
	k[n].mxn=n-1;
	mxn.push(n);
	for(int i=n-1;i>=1;i--)
		if(a[mxn.top()]<=a[i]){
			k[i].mxn=i-1;
			mxn.push(i);
		}
		else
		    k[i].mxn=mxn.top();
	mnn.push(1);
	for(int i=2;i<=n;i++)
	    if(a[mnn.top()]>=a[i]){
	    	k[i].mnn=i+1;
			mnn.push(i);
		}
		else
		    k[i].mnn=mnn.top();
	for(int i=1;i<=n;i++)
	    ans=max(ans,max(dfs(i,0),dfs(i,1)));
	printf("%lld",(ans==1)?0:ans);
    return 0;
}
/*
是某大佬提供的hack数据
5 
1 
2 
3 
1 
9
*/