この問題は、 スライド最小値 とよく似た考え方で解くことができます。

山を左から辿っていくことを考えます。この時、今見ている山から見える山の集合 \(S\) をうまく管理することを考えます。 \(S\) は山の標高の配列(を降順に並べたもの)として保持しておきます。

• 最初、 \(S\) は空である。
• \(i=1,2,\dots,N\) について、以下を繰り返す。
  • この時点で、 \(S\) は山 \(i-1\) から見えている山の集合であることに留意する。
  • \(S\) が空でなく、 \(S\) の末尾が \(H_i\) 以下である限り、以下を繰り返す。
    • \(S\) の末尾は \(H_i\) 以下なので、問題文中の条件 \(1\) より、山 \(i\) から見えることはない。また、条件 \(2\) より、山 \(i+1,i+2,\dots,N\) からこの山が見えることもない。
  • この時点で \(S\) に要素が残っていれば、それらの山は条件 \(1,2\) 双方を満たしているので、山 \(i\) から見える。よって、答えにこの時点での \(|S|\) を加算する。
  • \(S\) の末尾に \(H_i\) を追加する。
    • この追加があっても、 \(S\) は標高が降順に並んだ列であることを確認されたい。

全体で時間計算量 \(O(N)\) でこの問題に正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n;
  cin >> n;
  ll res=0;
  vector<ll> a;
  for(ll i=0;i<n;i++){
    ll h;
    cin >> h;
    while(!a.empty()){
      if(a.back()<=h){a.pop_back();}
      else{break;}
    }
    res+=a.size();
    a.push_back(h);
  }
  cout << res << "\n";
  return 0;
}