Intermediate.
Put your skills to the test.

Problem summary

For every building interval, count distinct buildings visible from at least one endpoint; equal or taller intervening buildings block visibility. Sum over all intervals.

Constraints

1≤N≤100000;1≤height[i]≤10^9.

Worked example

Input and output for the worked example discussed below.

4
4 2 3 2

18

Solution analysis

1. Count a building’s contribution across intervals instead of enumerating intervals. Find nearest left and right blockers L,R with height≥its height, using sentinels0,N+1.
2. Visibility from the left occurs in(i−L)(N−i+1) intervals, and from the right in i(R−i). Their intersection has(i−L)(R−i) intervals; subtract it to avoid counting the same visible building twice.
3. Two monotonic-stack scans find blockers in linear time; pop only strictly smaller heights, leaving equal heights as blockers. For[4,2,3,2], contributions4,4,6,4 total18.

Why it works

The nearest greater-or-equal blockers characterize exactly which endpoints see a building. Independent endpoint choices give the three product counts. Inclusion–exclusion counts visibility once per interval, and summing contributions equals summing interval scores.

Watch out. Equal heights block, so pop with<, not≤. Subtract the both-sides intersection and use1-based sentinel indices.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
using namespace std;
// The nearest greater-or-equal blockers characterize exactly which endpoints see a building.
int main(){
    int n;
    cin>>n;
    vector<int>a(n+1),left(n+1),right(n+1),stack;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        while(!stack.empty()&&a[stack.back()]<a[i]){
            stack.pop_back();
        }
        left[i]=stack.empty()?0:stack.back();
        stack.push_back(i);
    }
    stack.clear();
    for(int i=n;i>=1;i--){
        while(!stack.empty()&&a[stack.back()]<a[i]){
            stack.pop_back();
        }
        right[i]=stack.empty()?n+1:stack.back();
        stack.push_back(i);
    }
    long long answer=0;
    for(int i=1;i<=n;i++){
        long long l=1LL*(i-left[i])*(n-i+1),r=1LL*i*(right[i]-i),
                    both=1LL*(i-left[i])*(right[i]-i);
        answer+=l+r-both;
    }
    cout<<answer<<'\n';
}