单调栈（两边扩展）

#include <bits/stdc++.h>
#define ME(x , y) memset(x , y , sizeof(x))
#define SC scanf
#define rep(i ,j , n) for(int i = j ; i < n ; i ++)
#define red(i , n , j) for(int i = n-1 ; i >= j ; i--)
#define INF  0x3f3f3f3f
#define mod 998244353
#define PI acos(-1)
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
using namespace std;
typedef long long ll ;
const int MX = 1e5+9;
ll val[100009] , len[100009] ;//每一个元素和该元素的两边扩展额长度
ll s[100009] ,top ;//单调递减栈：记录每一个值向两边扩展的长度

 int main() {

     ll n ;
     while(cin >> n&&n){
        rep(i , 1 , n+1){
            scanf("%lld" , &val[i]);
            len[i] = 1 ;
        }
        val[n+1] = -1 , len[n+1] = 0 ;
        ll temp = 0 , ma = -1 , top = 0;
        rep(i , 1 , n+2){
            while(top && val[s[top-1]] >= val[i]){
                len[s[top-1]] += temp;//加上上一个弹栈的扩展长度（向右扩展长度）
                temp = len[s[top-1]];//记录该扩展长度
                ma = max(ma , len[s[top-1]] * val[s[top-1]]);
                top--;
            }
            len[i] += temp;（向左扩展长度）
            temp = 0;
            s[top++] = i ;
        }
        cout << ma << endl;
     }
 }