Sum of Every Minimum — Solution & Editorial

Back to the Problem

Each a_i is the minimum of (distance to previous strictly-smaller) × (distance to next smaller-or-equal) subarrays. Monotonic stacks compute both boundaries; sum a_i·left·right. The strict/non-strict asymmetry avoids double-counting equal values.

Complexity: O(N)

Watch out: Equal elements: one side must use strict and the other non-strict comparison, or subarrays are counted twice or zero times.