我们发现，如果要枚举一个区间，那么至少也是$O(n^2)$的

题目让我们求所有最小值的和

那么我们不妨$O(n)$去枚举序列，然后考虑每一个元素对答案的贡献

显然是当前这个值作为最小值的区间个数$*$这个值

于是我们对于序列的每个值，考虑以它作为区间最小值的区间个数

既然它是区间的最小值，那么显然这个区间没有比它更小的了

所以这个区间的活动范围就是这个数左边第一个比它小的数的位置$+1$到这个数的位置

举个锤子

1 3 5 2 4 8 9 8

以$2$作为最小值，显然$l$的活动范围是$[2,4]$

因为$1$不能在这个区间里，如果在这个区间里，那$2$就不是最小值，而且，$2$必须在这个区间里，因为我们统计的是2作为区间最小值的区间个数

$r$同理

于是，我们的问题就变成了对于每个数，如何快速知道左右两边第一个比它小的数的位置？？

单调栈啊

求出了l和r的范围，然后乘法原理就知道有多少个区间啦，然后直接统计就行了

值得注意的是，对于重复的数的处理

比如

2 2 2 2 2

有些区间会算重复

其实也很简单，让l和r的边界一个是小于，一个是小于等于就行了

比如第三个2，可以在左边找第一个小于2的，那么你l的左边界就是1，在右边找第一个小于等于2的，那么你的r就是3，这样就不会重复了

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cctype>
#define LL long long
LL in() {
    char ch; LL x = 0, f = 1;
    while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
    for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
    return x * f;
}
template<class T> bool chkmax(T &a, const T &b) { return a < b? a = b, 1 : 0; }
template<class T> bool chkmin(T &a, const T &b) { return b < a? a = b, 1 : 0; }
const int maxn = 1e6 + 10;
const int inf = 0x7fffffff;
class stack {
    protected:
        int st[maxn], tp;
    public:
        stack() { tp = 0; }
        void clear() { tp = 0; }
        int top() { return st[tp]; }
        void pop() { tp--; }
        bool empty() { return !tp; }
        void push(int x) { st[++tp] = x; }
}T;
int n;
LL ans, a[maxn];
int l[maxn], r[maxn];
int main() {
    n = in();
    for(int i = 1; i <= n; i++) a[i] = in();
    a[0] = a[n + 1] = -inf;
    T.push(0);
    for(int i = 1; i <= n; i++) {
        while(!T.empty() && a[i] <= a[T.top()]) T.pop();
        l[i] = T.top(); T.push(i);
    }
    T.clear(); T.push(n + 1);
    for(int i = n; i >= 1; i--) {
        while(!T.empty() && a[i] < a[T.top()]) T.pop();
        r[i] = T.top(); T.push(i);
    }
    for(int i = 1; i <= n; i++) ans += 1LL * (i - l[i]) * (r[i] - i) * a[i];
    printf("%lld\n", ans);
    return 0;
}