この問題は次の \(2\) つの問題に分解することができます。

問題1：各 \(i\) について、 \(i<j\) かつ \(A_i<A_j\) を満たす最小の \(j\) を求めよ

問題2： \(l,r\) が与えられるので、\(A_l,\dots,A_r\) の最小値を求めよ

前者は区間最大値を取得できるセグメントツリーを用い、各 \(i\) について \(x\) に関する条件「 \(A_i,\dots,A_x\) の最大値は \(A_i\) 以下か？」を二分探索することで求めることができます。

後者は区間最小値を取得できるセグメントツリーを用いて求めることができます。

どちらの操作も 1 回あたり \(O(\log N)\) で行えることから、\(O(N\log N)\) で解けました。

実装例 (C++)

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

int max_op(int x, int y){return max(x, y);}
int min_op(int x, int y){return min(x, y);}
int max_e(){return 0;}
int min_e(){return 2e9;}

int main(){
  int n;
  cin >> n;
  vector<int>h(n);
  for(int i=0; i<n; i++) cin >> h[i];

  atcoder::segtree<int, max_op, max_e> max_seg(h);
  atcoder::segtree<int, min_op, min_e> min_seg(h);

  long long ans = 0;
  for(int i=0; i<n; i++){
    auto f=[&](int x){return x <= h[i];};
    int j = max_seg.max_right(i, f);
    if(j != n){
      ans += min_seg.prod(i, j);
    }
  }
  cout << ans << endl;
}

実装例 (Python)

from atcoder.segtree import SegTree
N = int(input())
H = list(map(int, input().split()))

max_seg = SegTree(max, 0, H)
min_seg = SegTree(min, 10**10, H)

ans = 0
for i in range(N):
  j = max_seg.max_right(i, lambda v: v<=H[i])
  if j != N:
    ans += min_seg.prod(i, j)

print(ans)