#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#define debuga(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define assume(expr) ((!!(expr))||(exit((fprintf(stderr,"Assumption Failed: %s on Line %d\n",#expr,__LINE__),-1)),false))
#define range basic_string_view
using namespace std; typedef long long ll;
constexpr int N=3e5+5;
int n,a[N],L[N],R[N],fa[N],dep[N],sub[N]; vector<int> son[N]; ll ans[N];
signed main(){
    atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;}); ios::sync_with_stdio(0); cin.tie(0);
    cin>>n; For(i,1,n) cin>>a[i];
    stack<int> st; For(i,1,n) { while(st.size()&&a[i]>a[st.top()]) st.pop();; if(st.size()) L[i]=st.top();; st.push(i); }
    st=move(stack<int>());
    Rev(i,n,1) { while(st.size()&&a[i]>a[st.top()]) st.pop();; if(st.size()) R[i]=st.top();; st.push(i); }
    For(i,1,n) fa[i]=a[L[i]]>a[R[i]]?L[i]:R[i];
    debuga(L,1,n); debuga(R,1,n); debuga(fa,1,n);
    int rt=0; For(i,1,n) if(fa[i]) son[fa[i]].push_back(i); else rt=i;
    vector<int> lis; function<void(int)> dfs=[&](int u) { lis.push_back(u); for(int v:son[u]) dep[v]=dep[u]+1,dfs(v); }; dep[rt]=1; dfs(rt);
    reverse(lis.begin(),lis.end()); lis.pop_back();
    int tot=0; For(u,1,n) { tot+=dep[u]; sub[u]=1; }
    for(int u:lis) sub[fa[u]]+=sub[u];
    For(u,1,n) if(u!=rt) ans[max(1,L[u])]+=sub[u],R[u]&&(ans[R[u]+1]-=sub[u]);
    For(i,2,n) ans[i]+=ans[i-1];
    For(i,1,n) cout<<tot-ans[i]-1<<' ';; cout<<'\n';
    return 0;
}

// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// CONTINUE, NON-STOPPING, FOR CHARLIEVINNIE

// Started Coding On: October 30 Mon, 07 : 37 : 16