#include <bits/stdc++.h> using namespace std; const int N = 500050; int H[N],Stack[N]； long long Ans; int top; inline int Read(int ans=0,int f=0) { char c=getchar(); for(; c<'0' || c>'9'; f^=(c=='-'),c=getchar()); for(; c<='9' && c>='0'; c=getchar()) ans=(ans<<3)+(ans<<1)+(c^48); return f? -ans : ans; } void Calc(int x) { int L=0,R=top,pos=0; while(L<=R) { int mid=(L+R)>>1; if(H[Stack[mid]]>x) pos=mid,L=mid+1; else R=mid-1; } !pos? Ans+=top:Ans+=top-pos+1; } int main() { int n=Read(); for(int i=1; i<=n; ++i) H[i]=Read(); for(int i=1; i<=n; ++i) { Calc(H[i]); while(top>0 && H[i]>H[Stack[top]]) { --top; Stack[++top]=i; } printf("%lld\n",Ans); } }