单调栈的应用，向左右找离他最近的比他小的坐标存到q中

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 100010;
int n, h[N], l[N], r[N], q[N], tt;

int main()
{
    while(scanf("%d", &n), n)
    {
        for(int i=1;i<=n;i++) scanf("%d", &h[i]);
        tt = 0;
        q[0] = 0;
        h[0] = h[n + 1] = -1;
        for(int i=1;i<=n;i++)
        {
            while(h[i] <= h[q[tt]]) tt--;
            l[i] = q[tt];
            q[++tt] = i;
        }
        tt = 0;
        q[0] = n + 1;
        for(int i=n;i;i--)
        {
            while(h[i] <= h[q[tt]]) tt--;
            r[i] = q[tt];
            q[++tt] = i;
        }
        LL res = 0;
        for(int i=1;i<=n;i++) res = max(res, (LL)h[i] * (r[i] - l[i] - 1));
        printf("%lld\n", res);
    }
    return 0;
}