单调栈

基于递推，写起来更快

for(int i=1;i<=n;i++)
    scanf("%I64d",&a[i]),l[i]=r[i]=i;
a[0]=0;
for(int i=2;i<=n;i++){
    int now=i;
    while(now>1&&a[i]<=a[now-1]) now=l[now-1];
    l[i]=now;
}
for(int i=n-1;i;i--){
    int now=i;
    while(now<n&&a[i]<=a[now+1]) now=r[now+1];
    r[i]=now;
}