#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 2e5 + 5;

struct Info
{
    int maxPref, maxSuff;

    Info(){}
    Info(int x) : maxPref(x), maxSuff(x) {}
    Info(int maxPref, int maxSuff)
    {
        this->maxPref = maxPref;
        this->maxSuff = maxSuff;
    }

    void modifyPref(int x)
    {
        maxPref += x;
    }
    void modifySuff(int x)
    {
        maxSuff += x;
    }
};

Info operator +(const Info A, const Info B)
{
    return Info(max(A.maxPref, B.maxPref), max(A.maxSuff, B.maxSuff));
}

struct SegmentTree
{
    Info x;
    int lazyPref, lazySuff;

    int l, r;
    SegmentTree *L, *R;

    SegmentTree() : L(nullptr), R(nullptr), lazyPref(0), lazySuff(0) {}
    SegmentTree(int l, int r) : SegmentTree()
    {
        this->l = l;
        this->r = r;
    }

    void build(int val, int n)
    {
        if(l==r)
        {
            x = Info((l+1)*val, (n-r)*val);
            return;
        }

        L = new SegmentTree(l, (l+r)/2);
        R = new SegmentTree((l+r)/2+1, r);

        L->build(val, n);
        R->build(val, n);
        x = L->x + R->x;
    }

    void updateLazy()
    {
        x.modifyPref(lazyPref);
        x.modifySuff(lazySuff);
        if(l!=r)
        {
            L->lazyPref += lazyPref;
            L->lazySuff += lazySuff;
            R->lazyPref += lazyPref;
            R->lazySuff += lazySuff;
        }

        lazyPref = lazySuff = 0;
    }

    Info query(int ql, int qr)
    {
        updateLazy();

        if(l>=ql && r<=qr) return x;
        if(r<ql || l>qr) return Info(-MAXN, -MAXN);

        return L->query(ql, qr) + R->query(ql, qr);
    }

    void updatePref(int ql, int qr, int change)
    {
        updateLazy();

        if(l>=ql && r<=qr)
        {
            lazyPref += change;
            updateLazy();

            return;
        }
        if(r<ql || l>qr) return;

        L->updatePref(ql, qr, change);
        R->updatePref(ql, qr, change);
        x = L->x + R->x;
    }
    void updateSuff(int ql, int qr, int change)
    {
        updateLazy();

        if(l>=ql && r<=qr)
        {
            lazySuff += change;
            updateLazy();

            return;
        }
        if(r<ql || l>qr) return;

        L->updateSuff(ql, qr, change);
        R->updateSuff(ql, qr, change);
        x = L->x + R->x;
    }

    void update(int q, int change)
    {
        updatePref(q, r, change);
        updateSuff(l, q, change);
    }
};

int n;
int a[MAXN];
vector <int> num2Pos[MAXN];

int answer[MAXN];

void updateWithBiggerThanMiddle()
{
    SegmentTree *T = new SegmentTree(0, n-1);
    T->build(-1, n);

    for(int x = 1;x<=n;x++)
    {
        for(int i: num2Pos[x]) T->update(i, +2);
        for(int i: num2Pos[x])
        {
            int sum = 0;
            sum += T->query(i, n-1).maxPref - T->query(i, i).maxPref;
            sum += T->query(0, i).maxSuff - T->query(i, i).maxSuff;

            answer[i] = max(answer[i], sum/2);
        }
    }
}

void updateWithSmallerThanMiddle()
{
    SegmentTree *T = new SegmentTree(0, n-1);
    T->build(-1, n);

    for(int x = n;x>=1;x--)
    {
        for(int i: num2Pos[x]) T->update(i, +2);
        for(int i: num2Pos[x])
        {
            int sum = 0;
            sum += T->query(i, n-1).maxPref - T->query(i, i).maxPref;
            sum += T->query(0, i).maxSuff - T->query(i, i).maxSuff;

            answer[i] = max(answer[i], (sum+1)/2);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for(int i = 0;i<n;i++) 
    {
        cin >> a[i];
        num2Pos[a[i]].push_back(i);
    }

    updateWithBiggerThanMiddle();   
    updateWithSmallerThanMiddle();

    for(int i = 0;i<n;i++)
        cout << answer[i] << " ";
    cout << '\n';
}