P2866不知道为什么T了（原谅我是个蒟蒻所以检查不出来）

代码

#include<bits/stdc++.h>
using namespace std;
const int N=80001;
int n,h[N],logm[N],f[35][N];
long long ans;
inline int query(int l,int r){
	if(l>r) return false;
	else{
		int len=r-l+1;
		if(std::max(f[logm[len]][l],f[logm[len]][r-(1<<logm[len])+1])>h[l-1]) return true;
		else return false;
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>h[i];
		f[0][i]=h[i];
	}
	for(int i=2;i<=n;i++){
		logm[i]=logm[i>>1]+1;
	}
	for(int j=1;j<=logm[n];j++){
		for(int i=1;i+(j<<1)-1<+n;i++){
			f[j][i]=std::max(f[j-1][i],f[j-1][i+(1<<(j-1))]);
		}
	}
	for(int i=1;i<=n;i++){
		int l=i,r=n;
		while(l<=r){
			int mid=(l+r)/2;
			if((l+r)%2==1) mid++;
			if(query(i+1,mid)) l=mid;
			else r=mid-1;
		}
		ans+=std::max(0,l-i);
	}
	cout<<ans<<endl;
	return 0;
}