#include<bits/stdc++.h>
using namespace std;
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define int long long
#define re register int
#define inf 0x7fffffffffffffff
#define Pair pair<int,int>
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f==1?x:-x;
}
const int N=2e5+10;
struct Seg{
    int l,r,lm,rm,sum;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define lm(x) tree[x].lm
    #define rm(x) tree[x].rm
    #define sum(x) tree[x].sum
}tree[N<<2];
inline void pushup(int p)
{
    sum(p)=sum(p<<1)+sum(p<<1|1);
    lm(p)=max(lm(p<<1),sum(p<<1)+lm(p<<1|1));
    rm(p)=max(rm(p<<1|1),sum(p<<1|1)+rm(p<<1));
}
void build(int p,int l,int r)
{
    l(p)=l;r(p)=r;
    if(l==r)return sum(p)=lm(p)=rm(p)=-1,void();
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}
void change(int p,int pos,int x)
{
    if(l(p)==r(p))return sum(p)=lm(p)=rm(p)=x,void();
    int mid=(l(p)+r(p))>>1;
    if(pos<=mid)change(p<<1,pos,x);
    else change(p<<1|1,pos,x);
    pushup(p);
}
Seg query(int p,int l,int r)
{
    if(r(p)<l || r<l(p))return {0,0,0,0,0};
    if(l<=l(p) && r>=r(p))return tree[p];
    Seg a=query(p<<1,l,r),b=query(p<<1|1,l,r);
    return {min(a.l,b.l),max(a.r,b.r),max(a.lm,a.sum+b.lm),max(b.rm,b.sum+a.rm),a.sum+b.sum};
}
int n,ans[N];
struct node{int x,id;}a[N];
bool cmp(node a,node b){return a.x<b.x;}
void calc(int flag)
{
    build(1,1,n);
    for(re i=1;i<=n;++i)
    {
        int j=i;
        while(j<n && a[j+1].x==a[i].x)++j;
        for(re k=i;k<=j;++k) change(1,a[k].id,1);
        for(re k=i;k<=j;++k)
        {
            Seg p=query(1,1,a[k].id),q=query(1,a[k].id,n);
            ans[a[k].id]=max(ans[a[k].id],p.rm+q.lm-1-!flag);
        }
        i=j;
    }
}
signed main()
{
    n=read();
    for(re i=1;i<=n;++i)
        a[i].x=read(),a[i].id=i;
    sort(a+1,a+n+1,cmp);
    calc(0);
    for(re i=1;i<=n/2;++i) swap(a[i],a[n-i+1]);
    for(re i=1;i<=n;++i) a[i].x=-a[i].x;
    calc(1);
    for(re i=1;i<=n;++i) 
        printf("%lld ",ans[i]/2);
    return 0;
}

您必须遵守各项服务中提供的所有政策（包括但不限于讨论和题解的版规）。 请合理使用我们的服务。对于滥用行为，我们有权在不另行通知的情况下封禁/删除相关账号及其上传/生成的相关数据。滥用行为包括但不限于：

• 干扰我们的服务或使用除我们提供的界面和指示以外的方法访问这些服务；
• 使用我们服务中出现的缺陷干扰其他网站或设施的正常运行；
• 使用代理池/账号池等绕过限制的行为；
• 将相关服务用于不合理行为（如使用个人文件或题目文件功能来存储/分发无关的文件）；
• 使用临时邮箱或小号进行注册，干扰信息源追溯；
• 未经允许使用自动化脚本对站点内容进行大批量爬取；
• 除由管理员提供的账户外，进行任何形式的账号共享；
• 其他法律法规所禁止的行为。

您在使用我们服务时须遵守我们服务器所在地的法律法规，不得利用我们服务从事违法违规行为，包括但不限于：

• 发布、传送、传播、储存危害国家安全统一、破坏社会稳定、违反公序良俗、侮辱、诽谤、淫秽、暴力以及任何违反国家法律法规的内容；
• 发布、传送、传播、储存侵害他人知识产权、商业秘密等合法权利的内容；
• 恶意虚构事实、隐瞒真相以误导、欺骗他人；
• 发布、传送、传播广告信息及垃圾信息；
• 其他法律法规禁止的行为。