【bzoj1660】【单调栈】Bad Hair Day 乱发节

* Line 1: 牛的数量 N。

 * Lines 2..N+1: 第 i+1 是一个整数，表示第i头牛的高度。

* Line 1: 一个整数表示c[1] 至 c[N]的和。

#include<iostream>
#include<cstdio>
using namespace std;
int n,top,a[80001],s[80001];
long long ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
       scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        if(a[i]<s[top])
            ans+=top;
        else
        {
            while(a[i]>=s[top]&&top)
                top--;
            ans+=top;
        }
        s[++top]=a[i];
    }
    printf("%lld",ans);
    return 0;
}