这份代码的主题思路下面写了。里面加了两个优化： 1.如果某一个a的“势力范围”中，有一侧为空，那么跳过； 2.如果只有一个元素，不进行排序，避免大量调用STL库函数出问题

没用什么高级数据结构，也没刻意卡常，理论上可以卡到O(n^2 log),但加了这两个优化跑的还挺快的。蒟蒻并不会证这份代码的时间复杂度。如果过路的大神看到了这份代码，发现这个代码复杂度是对的，给蒟蒻讲讲时间复杂度的证明呗qwq。如果发现这份代码时间复杂度是错的，就赶快告诉蒟蒻，别影响其他人qwq。感谢大佬们

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
typedef long long LL;
il int read()
{
	int s=0,w=1;char c=getchar();
	while(c<'0'||c>'9'){ if(c=='-') w=-1;c=getchar(); }
	while(c>='0'&&c<='9'){ s=(s<<1)+(s<<3)+c-'0';c=getchar();}
	return s*w;
}
const int N=1e5+10;
int n,a[N],sum[N];
LL ans;
int zhan[N],n_zh,L[N],R[N];
int c[N];
il bool cmp(int x,int y){ return x>y; }
int main()
{
	n=read();
	for(re int i=1;i<=n;i++){
		a[i]=read();
		sum[i]=(a[i]==1)?sum[i-1]+1:sum[i-1];
	}
	n_zh=0,zhan[0]=0;
	for(re int i=1;i<=n;i++){
		while(n_zh && a[zhan[n_zh]]<=a[i]) n_zh--;
		L[i]=zhan[n_zh];
		zhan[++n_zh]=i;
	}
	n_zh=0,zhan[0]=n+1;
	for(re int i=n;i>=1;i--){
		while(n_zh && a[zhan[n_zh]]<a[i]) n_zh--;
		R[i]=zhan[n_zh];
		zhan[++n_zh]=i;
	}
	for(re int i=1;i<=n;i++){
		ans+=sum[R[i]-1]-sum[L[i]];
		if((i-L[i]-1)<=0 || (R[i]-i-1)<=0) continue;
		for(re int j=L[i]+1;j<R[i];j++) c[j]=a[j];
		if(i-L[i]-1>1) sort(c+L[i]+1,c+i);
		if(R[i]-i-1>1) sort(c+i+1,c+R[i],cmp);
		int pl=L[i]+1,pr=i+1;
		while(pl<i){
			while(pr<R[i] && 1LL*c[pr]*c[pl]>1LL*a[i]) pr++;
			ans+=1LL*R[i]-pr;
			pl++;
		}
	}
	printf("%lld",ans);
	return 0;
}
/*
朴素想法是，枚举两个数对，验证是否合法，复杂度n^2
但是看到这个题的数据范围，显然不能这么搞。
然后就考虑枚举最大值，对每一个最大值计算有多少个数对
的最大a值为该点。
首先一遍单调栈预处理出每个a值的“势力范围”,
也就是a在什么范围内是最大值 
然后对于每一个a值，扫描两侧可以被自己影响的a值，
然后进行排序，左侧单调递增排序，右侧单调递减排序 
双指针扫一下就搞定。注意，除非a的“势力范围”中有1，
否则a本身不能作端点，所以需要预处理一下1的个数。 
复杂度为O(nlog)级，如果想卡感觉可以卡到O(n^2 log)
但实际上应该接近O(n)。
*/