太久没见过启发式合并了，然后没想出做法。
首先笛卡尔树建出来。
然后直接枚举跨过 \(mid\) 的长度为 \(a_{mid}\) 的区间，RMQ \(O(1)\) 验证即可。
发现这样的区间个数不超过左右区间大小的较小值，时间复杂度：\(O(n\log n)\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=3e5+10,K=__lg(N)+2;
int n,a[N],buf[N],f[K][N];
int top,stk[N],ls[N],rs[N],L[N],R[N];
bool chk(int l,int r){
int k=__lg(r-l+1);
return max(f[k][l],f[k][r-(1<<k)+1])<l;
}
int ans;
void dfs(int u){
if(ls[u])dfs(ls[u]),L[u]=L[ls[u]];
else L[u]=u;
if(rs[u])dfs(rs[u]),R[u]=R[rs[u]];
else R[u]=u;
int st=L[u],ed=u;
st=max(st,u-a[u]+1),ed=min(ed,R[u]-a[u]+1);
for(int i=st;i<=ed;i++)ans+=chk(i,i+a[u]-1);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)f[0][i]=buf[a[i]],buf[a[i]]=i;
for(int i=1;(1<<i)<=n;i++)for(int j=1;j+(1<<i)-1<=n;j++)
f[i][j]=max(f[i-1][j],f[i-1][j+(1<<i-1)]);
for(int i=1;i<=n;i++){
for(;top&&a[stk[top]]<a[i];top--)ls[i]=stk[top];
rs[stk[top]]=i,stk[++top]=i;
}
dfs(rs[0]);
cout<<ans;
return 0;
}