题意
Farmer John的奶牛在风中凌乱了它们的发型……
每只奶牛都有一个身高hi(1 ≤ hi ≤ 1,000,000,000)，现在在这里有一排全部面向右方的奶牛，一共有N只(1 ≤ N ≤ 80,000)。对于奶牛i来说，如果奶牛i+1，i+2，……，N这些奶牛的身高严格小于奶牛i，则奶牛i可以看到它们凌乱的发型。
输入
第一行 奶牛数量N
第二到 N+1行：第i+1行输入奶牛i的身高
输出
第一行：一个整数即c1到cN的和
样例输入
6
10
3
7
4
12
2
样例输出
5
分析
方法一
对于i，我们知道，令j∈[i+1,n]，s=max(hi+1....hj)是具有单调性的（感性理解，j越大数字越多，同时j更小时的数也没有丢掉），所以如果s<=h[i]时，就可以继续向右扩张。使用二分查找，RMQ查询。RMQ可以使用ST达到O(1)的查询。
方法二
一头牛看到多少牛不好做，但可以被多少牛看到可解。只要在左边形成一个递减的数列，且最后一个大于当前的牛即可，数列大小即为当前牛的答案。可以用单调栈维护。
代码（法一）
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define RG register ll
#define rep(i,a,b) for(RG i=a;i<=b;++i)
#define per(i,a,b) for(RG i=a;i>=b;--i)
#define ll unsigned long long
#define inf (1<<29)
#define maxn 80005
#define ls (pos<<1)
#define rs (pos<<1|1)
#define mid ((t[pos].l+t[pos].r)>>1)
using namespace std;
ll n,ANS;
ll num[maxn],mx[maxn][];
inline ll read()
{
ll x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
/*
void build(ll pos,ll l,ll r)
{
t[pos].l=l,t[pos].r=r;
if(l==r) {t[pos].mx=num[l];return;}
build(ls,l,mid);build(rs,mid+1,r);
t[pos].mx=max(t[ls].mx,t[rs].mx);
} ll query(ll pos,ll l,ll r)
{
if(l<=t[pos].l&&t[pos].r<=r) return t[pos].mx;
ll ans=0;
if(l<=mid) ans=query(ls,l,r);
if(r>mid) ans=max(ans,query(rs,l,r));
return ans;
}
*/ void ST()
{
rep(i,,n) mx[i][]=num[i];
rep(j,,)
rep(i,,n)
if(i+(<<j)-<=n)
mx[i][j]=max(mx[i][j-],mx[i+(<<(j-))][j-]);
} int query(int l,int r)
{
int len=log(r-l+)/log();
return max(mx[l][len],mx[r-(<<len)+][len]);
} int main()
{
n=read();
rep(i,,n) num[i]=read();
//build(1,1,n);
ST();
rep(i,,n)
{
RG l=i+,r=n,ans=i,md;
while(l<=r)
{
md=(l+r)>>;
if(query(i+,md)<num[i]) ans=md,l=md+;
else r=md-;
}
ANS+=ans-i;
}
cout<<ANS;
return ;
}