有大佬能帮忙看一下复杂度是 $O(n)$ 的吗，怕分析错了。

#include<bits/stdc++.h>
using namespace std;

namespace FAST_IO{
	#define Get() (BUF[Pin++])
	const int LEN=1<<20;
	char BUF[LEN];
	int Pin=LEN;
	inline void flushin(){memcpy(BUF,BUF+Pin,LEN-Pin),fread(BUF+LEN-Pin,1,Pin,stdin),Pin=0;return;}
	inline char Getc(){return (Pin==LEN?(fread(BUF,1,LEN,stdin),Pin=0):0),BUF[Pin++];}
	template<typename tp=int>inline tp read(){(Pin+32>=LEN)?flushin():void();tp res=0;char f=1,ch=' ';for(;ch<'0'||ch>'9';ch=Get())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=Get())res=(res<<3)+(res<<1)+ch-48;return res*f;}
}
using namespace FAST_IO;

const int N=1e6+10;
int n,a[N],ch[N][2],L[N],R[N],stk[N],top,mx;
long long ans;
void solve(int l,int r,int p)
{
	if(l>=r)return;
	int pl=p-1,pr=p;
	while(L[pl]>=l&&R[pr]<=r)
	{
		while(R[pr]<=r&&a[R[pr]]>a[pl])pr=R[pr];
		ans+=1ll*(pl-L[pl])*(min(r,R[pr]-1)-p+1);
		pl=L[pl];
	}
	while(R[pr]<=r&&a[R[pr]]>a[pl])pr=R[pr];
	ans+=1ll*(pl-l+1)*(min(r,R[pr]-1)-p+1);
	solve(l,p-1,ch[p][0]);
	solve(p+1,r,ch[p][1]);
	return;
}
int main()
{
	freopen("E.in","r",stdin);
//	freopen("E_.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++) if(a[i]==n) mx=i;
	top=0;
	for(int i=1;i<=n;i++)
	{
		while(top&&a[stk[top]]<a[i])top--;
		if(top&&a[ch[stk[top]][1]]<a[i])ch[stk[top]][1]=i;
		stk[++top]=i;
	}
	top=0;
	for(int i=n;i;i--)
	{
		while(top&&a[stk[top]]<a[i])top--;
		if(top&&a[ch[stk[top]][0]]<a[i])ch[stk[top]][0]=i;
		stk[++top]=i;
	}
	top=0;
	for(int i=1;i<=n;i++)
	{
		while(top&&a[stk[top]]>a[i])top--;
		L[i]=stk[top];
		stk[++top]=i;
	}
	top=0;
	for(int i=n+1;i;i--)
	{
		while(a[stk[top]]>a[i]&&top)top--;
		R[i]=stk[top];
		stk[++top]=i;
	}
	solve(1,n,mx);
	cout<<ans<<'\n';
	return 0;
}