分析

对于每个端点维护四个单调栈。表示这个端点作为最小值，最大值可以满足的合法区间 。那么只有 在 的合法区间内， 在 的合法区间内，这个用扫描线维护一下就好了，要记住先加后减，否则会丢掉重合的方案。

一些理解

• 是我这个点可以延展的范围。如果我都不能到 ，那么我肯定不能作为端点出现。所以需要判断 同理。
• 假如我已经知道了以 为左端点,的右端点可选的区间范围是 ,也知道以 为右端点,的左端点可选的区间范围是 ，然后差分找答案。
• 先钦定考虑 这个二元组的贡献。考虑这个值作为最小值可以的区间。再考虑这个作为最大值合法的方案。用差分维护区间。
  

  代码

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 1e6 + 100;
int read() {int x;scanf("%lld",&x);return x;}
int st[N],top,mxr[N],mxl[N],mil[N],mir[N];
int t[N],a[N],n;
void add(int x,int d) {for(int i = x;i<=n;i+=i&-i) t[i]+=d;}
int ask(int x) {int tot=0;for(int i=x;i;i-=i&-i)tot+=t[i];return tot;}
vector<int> L[N],R[N],W[N];
signed main() {
    n = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    for(int i = 1;i <= n;i++) {
        while(top && a[st[top]] > a[i]) top--;
        mil[i] = top?st[top] + 1:1;st[++top] = i;
    }
    top = 0;
    for(int i = 1;i <= n;i++) {
        while(top && a[st[top]] < a[i]) top--;
        mxl[i] = top?st[top] + 1:1;st[++top] = i;
    }
    top = 0;
    for(int i = n;i >= 1;i--) {
        while(top && a[st[top]] > a[i]) top--;
        mir[i] = top?st[top] - 1:n;st[++top] = i;
    }
    top = 0;
    for(int i = n;i >= 1;i--) {
        while(top && a[st[top]] < a[i]) top--;
        mxr[i] = top?st[top] - 1:n;st[++top] = i;
    }
    for(int i = 1;i <= n;i++) {
        if(mil[i] <= a[i] && a[i] <= mir[i]) L[mil[i]].push_back(a[i]),R[mir[i]].push_back(a[i]);
        if(mxl[i] <= a[i] && a[i] <= mxr[i]) W[a[i]].push_back(i); 
    }
    long long ans = 0; 
    for(int i = 1;i <= n;i++) {
        for(auto x:L[i]) add(x,1);
        for(auto x:W[i]) ans += ask(mxr[x]) - ask(mxl[x]-1);
        for(auto x:R[i]) add(x,-1); 
    }
    cout << ans << endl;

}