#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 1e9;
const int N = 200200;

template <typename type>
struct SegmentTreeLazy {
#define Mid ((L + R) >> 1)
#define Left (Node << 1)
#define Right (Node << 1 | 1)

   private:
    const type E = -INF;           /// identity element            /// Check this
    const type EL = 0;             /// identity element for lazy   /// Check this
    static const int Nax = 4 * N;  /// Check this

    int n;  /// Array length
    type Tree[Nax];
    type Lazy[Nax];

   public:
    SegmentTreeLazy(int n = 0) : n(n) {
        for (int Node = 0; Node < Nax; Node++)
            Tree[Node] = E, Lazy[Node] = EL;
    }

   private:
    type Unite(type x, type y) {  /// Check this
        return max(x, y);
    }

   private:
    void Merge(int Node) {
        Tree[Node] = Unite(Tree[Left], Tree[Right]);
    }

   private:
    void PushLazy(int Node, int Len) {
        if (Lazy[Node] != EL) {
            Tree[Node] += Lazy[Node];  /// Check this
            if (Len > 1) {
                Lazy[Left] += Lazy[Node];   /// Check this
                Lazy[Right] += Lazy[Node];  /// Check this
            }
            Lazy[Node] = EL;
        }
    }

   public:
    void Build(const vector<type>& a) {
        Clear();
        n = a.size();
        Build(a, 1, 0, n - 1);
    }

   private:
    void Build(const vector<type>& a, int Node, int L, int R) {
        Tree[Node] = E, Lazy[Node] = EL;
        if (L == R)
            return void(Tree[Node] = a[L]);
        Build(a, Left, L, Mid);
        Build(a, Right, Mid + 1, R);
        Merge(Node);
    }

   public:
    void Update(int i, int j, type x) {
        if (i < 0)
            i = 0;
        if (j >= n)
            j = n - 1;
        if (n <= 0 || i > j)
            return;
        Update(i, j, x, 1, 0, n - 1);
    }

   private:
    void Update(int i, int j, type x, int Node, int L, int R) {
        PushLazy(Node, R - L + 1);
        if (j < L || R < i)
            return;
        if (i <= L && R <= j)
            return Lazy[Node] = x, PushLazy(Node, R - L + 1);
        Update(i, j, x, Left, L, Mid);
        Update(i, j, x, Right, Mid + 1, R);
        Merge(Node);
    }

   public:
    type Query(int i, int j) {
        if (i < 0)
            i = 0;
        if (j >= n)
            j = n - 1;
        if (n <= 0 || i > j)
            return E;
        return Query(i, j, 1, 0, n - 1);
    }

   private:
    type Query(int i, int j, int Node, int L, int R) {
        PushLazy(Node, R - L + 1);
        if (j < L || R < i)
            return E;
        if (i <= L && R <= j)
            return Tree[Node];
        return Unite(Query(i, j, Left, L, Mid), Query(i, j, Right, Mid + 1, R));
    }

   private:
    void Clear() {
        for (int Node = 0; Node <= 4 * n; Node++)
            Tree[Node] = E, Lazy[Node] = EL;
        n = 0;
    }

#undef Mid
#undef Left
#undef Right
};

int a[N];
int answer[N];
vector<int> idx[N];
SegmentTreeLazy<int> tree[2];

void maximize(int& x, int y) {
    if (x < y) {
        x = y;
    }
}

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        idx[a[i]].push_back(i);
    }

    vector<int> base(n + 1);
    for (int k1 = 0; k1 < 2; k1++) {
        for (int i = 0; i <= n; i++) {
            base[i] = (k1 ? -i : +i);
        }
        tree[k1].Build(base);
    }

    for (int x = 1; x <= n; x++) {
        for (int i : idx[x]) {
            for (int k1 = 0; k1 < 2; k1++) {
                tree[k1].Update(i, n, k1 ? +2 : -2);
            }
        }

        for (int i : idx[x]) {
            for (int k1 = 0; k1 < 2; k1++) {
                tree[k1].Update(i, n, k1 ? -1 : +1);
            }

            int result = tree[0].Query(0, i - 1) + tree[1].Query(i, n);
            maximize(answer[i], result / 2);

            for (int k1 = 0; k1 < 2; k1++) {
                tree[k1].Update(i, n, k1 ? +1 : -1);
            }
        }
    }

    for (int k1 = 0; k1 < 2; k1++) {
        for (int i = 0; i <= n; i++) {
            base[i] = (k1 ? +i : -i);
        }
        tree[k1].Build(base);
    }

    for (int x = 1; x <= n; x++) {
        for (int i : idx[x]) {
            for (int k1 = 0; k1 < 2; k1++) {
                tree[k1].Update(i, n, k1 ? -1 : +1);
            }

            int result = tree[0].Query(0, i - 1) + tree[1].Query(i, n);
            maximize(answer[i], (result + 1) / 2);

            for (int k1 = 0; k1 < 2; k1++) {
                tree[k1].Update(i, n, k1 ? +1 : -1);
            }
        }

        for (int i : idx[x]) {
            for (int k1 = 0; k1 < 2; k1++) {
                tree[k1].Update(i, n, k1 ? -2 : +2);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        printf("%d%c", answer[i], " \n"[i == n]);
    }
}