Vasya has an array of n integers a_1, a_2, …, a_n. Vasya thinks that all numbers in his array are strange for some reason. To calculate how strange the i-th number is, Vasya created the following algorithm.

He chooses a subsegment a_l, a_{l+1}, …, a_r, such that 1 ≤ l ≤ i ≤ r ≤ n, sort its elements in increasing order in his head (he can arrange equal elements arbitrary). After that he finds the center of the segment. The center of a segment is the element at position (l + r) / 2, if the length of the segment is odd, and at position (l + r + 1) / 2 otherwise. Now Vasya finds the element that was at position i before the sorting, and calculates the distance between its current position and the center of the subsegment (the distance between the elements with indices j and k is |j - k|).

The strangeness of the number at position i is the maximum distance among all suitable choices of l and r. 

Vasya wants to calculate the strangeness of each number in his array. Help him to do it. 

Input

The first line contains a single integer n (1 ≤ n ≤ 200 000) — the size of the array.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n) — Vasya's array.

Output

Print a single line with n numbers. The i-th of them must be equal to the strangeness of the i-th element of the array.

Examples

Input


5
5 4 3 2 1


Output


2 1 1 2 2 


Input


7
3 6 5 6 2 1 3


Output


2 3 1 3 2 3 1 

Note

In the first example:

  1. For the first position we choose the segment from 1 to 5. After sorting, it looks like [1, 2, 3, 4, 5], the center is 3. The distance from the center to 5 is 2.
  2. For the second position we choose the segment from 2 to 4.
  3. For the third position we choose the segment from 3 to 5.
  4. For the fourth position we choose the segment from 1 to 4. After sorting, it looks like [2, 3, 4, 5], the center is 4. The distance from the center to 2 is 2. 
  5. For the fifth position we choose the segment from 1 to 5.
#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#endif
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define LL long long
#define LD long double
#define Complex complex<double>
#define y1 ___y1
#define next ___next
#define left ___left
#define right ___right
#define pii pair<int, int>
#define pll pair<LL, LL>
#define pdd pair<double, double>
#define pldld pair<LD, LD>
#define vi vector<int>
#define vl vector<LL>
#define vii vector<pii>
#define vll vector<pll>
#define PQ priority_queue
#define ffo fflush(stdout)
#define gch getchar()
#define e (int)(1e9 + 7)
#define MOD (int)(1e9 + 7)
#define e2 (double)2.71828182846
#define pi (double)3.14159265358979
#define ri(X) scanf("%d", &(X))
#define rii(X, Y) scanf("%d%d", &(X), &(Y))
#define riii(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define rl(X) scanf("%lld", &(X))
#define rll(X, Y) scanf("%lld%lld", &(X), &(Y))
#define rlll(X, Y, Z) scanf("%lld%lld%lld", &(X), &(Y), &(Z))
#define printi(X) printf("%d", (int)(X))
#define printii(X, Y) printf("%d %d", (int)(X), (int)(Y))
#define printiii(X, Y, Z) printf("%d %d %d", (int)(X), (int)(Y), (int)(Z))
#define printl(X) printf("%lld", (LL)(X))
#define printll(X, Y) printf("%lld %lld", (LL)(X), (LL)(Y))
#define printlll(X, Y, Z) printf("%lld %lld %lld", (LL)(X), (LL)(Y), (LL)(Z))
#define enter printf("\n")
#define space printf(" ")
struct matrix {
    int sz;
    LL a[105][105];
    matrix& operator = (const matrix &T) {
        sz = T.sz;
        for (int i = 1; i <= sz; i++) {
            for (int j = 1; j <= sz; j++) {
                a[i][j] = T.a[i][j];
            }
        }
        return *this;
    }
    matrix operator + (const matrix &T) const {
        matrix ans;
        ans.sz = sz;
        for (int i = 1; i <= sz; i++) {
            for (int j = 1; j <= sz; j++) {
                ans.a[i][j] = a[i][j] + T.a[i][j];
                ans.a[i][j] %= e;
            }
        }
        return ans;
    }
    matrix operator * (const matrix &T) const {
        matrix ans;
        ans.sz = sz;
        for (int i = 1; i <= sz; i++) {
            for (int j = 1; j <= sz; j++) {
                ans.a[i][j] = 0;
                for (int k = 1; k <= sz; k++) {
                    ans.a[i][j] += a[i][k] * T.a[k][j];
                    ans.a[i][j] %= e;
                }
            }
        }
        return ans;
    }
    matrix I() {
        matrix ans;
        ans.sz = sz;
        for (int i = 1; i <= sz; i++) {
            for (int j = 1; j <= sz; j++) {
                if (i == j) ans.a[i][j] = 1;
                else ans.a[i][j] = 0;
            }
        }
        return ans;
    }
    matrix power(LL p) {
        if (p == 0) return I();
        if (p == 1) return *this;
        matrix tmp = power(p / 2);
        if (p % 2) tmp = tmp * tmp * (*this);
        else tmp = tmp * tmp;
        return tmp;
    }
    void print() {
        for (int i = 1; i <= sz; i++) {
            for (int j = 1; j <= sz; j++) {
                printf(j == sz? "%lld\n" : "%lld ", a[i][j]);
            }
        }
        return;
    }
};
struct polynomial {
    vector<Complex> v;
    int sz;
    polynomial operator * (const polynomial &T) const {
        polynomial ans;
        if (sz >= T.sz) {
            ans = *this;
            for (int i = 0; i < T.sz; i++) {
                ans.v[i] *= T.v[i];
            }
        }
        else {
            ans = T;
            for (int i = 0; i < sz; i++) {
                ans.v[i] *= v[i];
            }
        }
        return ans;
    }
};
inline polynomial FFT(polynomial a) {
    if (a.sz <= 1) return a;
    polynomial even, odd;
    even.sz = odd.sz = 0;
    for (int i = 0; i < a.sz; i += 2) {
        even.v.pb(a.v[i]);
        even.sz++;
    }
    for (int i = 1; i < a.sz; i += 2) {
        odd.v.pb(a.v[i]);
        odd.sz++;
    }
    polynomial Even = FFT(even);
    polynomial Odd = FFT(odd);
    polynomial ans;
    ans.sz = a.sz;
    for (int i = 0; i < ans.sz; i++) {
        ans.v.pb(0);
    }
    for (int i = 0; i < a.sz / 2; i++) {
        Complex w = polar(1.0, -2 * pi * i / a.sz) * Odd.v[i];
        ans.v[i] = Even.v[i] + w;
        ans.v[i + a.sz / 2] = Even.v[i] - w;
    }
    return ans;
}
inline polynomial IFFT(polynomial a) {
    for (int i = 0; i < a.sz; i++) {
        a.v[i] = conj(a.v[i]);
    }
    polynomial ans = FFT(a);
    for (int i = 0; i < a.sz; i++) {
        ans.v[i] = conj(ans.v[i]);
        ans.v[i] /= ans.sz;
    }
    return ans;
}
typedef struct CH_Remainder {
	LL result, mod_num; //find target so target % mod_num = result, need /gcd
} CH_Remainder, ch_remainder[105];
inline LL ex_gcd(LL a, LL b, LL &x, LL &y) {
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}
	LL r = ex_gcd(b, a % b, x, y);
	LL t = x;
	x = y;
	y = t - a / b * y;
	return r;
}
inline LL mod_reverse(LL a, LL n) {
	LL d, x, y;
	d = ex_gcd(a, n, x, y);
	if (d == 1) return (x % n + n) % n;
	else return -1;
} 
inline LL CRT(ch_remainder a) {
	LL k = a[0].mod_num;
	LL b = 0, z = 0;
	for (int i = 1; a[i].mod_num; i++) {
		k *= a[i].mod_num;
	}
	for (int i = 0; a[i].mod_num; i++) {
		z = mod_reverse(k / a[i].mod_num, a[i].mod_num);
		if (z == -1) return -1;
		b += (a[i].result * (k / a[i].mod_num) * z);
	}
	return b % k;
}
struct polygon {
    int n;
    pii a[1005];
    double area() {
        double d1 = 0, d2 = 0;
        for (int i = 0; i < n; i++) {
            d1 += a[i].x * a[(i + 1) % n].y;
            d2 += a[(i + 1) % n].x * a[i].y;
        }
        return (d1 - d2) / 2;
    }
    bool inside(pldld p) {
        int ct = 0;
        LD d;
        pldld p1 = a[0];
        for (int i = 1; i <= n; i++) {
            pldld p2 = a[i % n];
            if (p.y > min(p1.y, p2.y) && p.y <= max(p1.y, p2.y) && p.x <= max(p1.x, p2.x) && p1.y != p2.y) {
                d = (p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x;
                if (p1.x == p2.x || p.x <= d) ct++;
            }
            p1 = p2;
        }
        return ct % 2;
    }
};
struct graph {
    #define SZ 1005
    int n;
    vi v[SZ];
    int vis[SZ], low[SZ], t;
    int indeg[SZ];
    stack<int> st;
    int top = 0;
    bool instack[SZ];
    int to[SZ];
    void tarjanDFS(int x) {
        vis[x] = low[x] = ++t;
        st.push(x);
        instack[x] = true;
        for (auto i : v[x]) {
            if (!vis[i]) tarjanDFS(i);
            if (instack[i]) { // still no SCC
                low[x] = min(low[x], low[i]);
            }
        }
        if (vis[x] == low[x]) { // form SCC
            int i;
            do {
                i = st.top();
                st.pop();
                instack[i] = false;
                to[i] = x;
            } while (i != x);
        }
    }
    void tarjan() {
        memset(vis, 0, sizeof(vis));
        t = 0;
        for (int i = 1; i <= n; i++) { //1 to n
            if (!vis[i]) tarjanDFS(i);
        }
        return;
    }
    void calIndeg() {
        for (int i = 1; i <= n; i++) { //1 to n
            for (auto j : v[i]) indeg[j]++;
        }
        return;
    }
};
struct segtree {
    int l, r, mid;
    LL lazy = 0;
    LL mn = 0, mx = 0;
    segtree *lc, *rc;
    segtree(int L, int R) {
        l = L;
        r = R;
        mid = (l + r) / 2;
        if (l != r) {
            lc = new segtree(l, mid);
            rc = new segtree(mid + 1, r);
        }
    }
    void apply(LL X) {
        mn += X;
        mx += X;
        lazy += X;
    }
    void push() {
        if (l == r) return;
        lc->apply(lazy);
        rc->apply(lazy);
        lazy = 0;
    }
    void update(int L, int R, LL X) {
        push();
        if (l == L && r == R) {
            apply(X);
            return;
        }
        else if (R <= mid) lc->update(L, R, X);
        else if (L >= mid + 1) rc->update(L, R, X);
        else {
            lc->update(L, mid, X);
            rc->update(mid + 1, R, X);
        }
        mn = min(lc->mn, rc->mn);
        mx = max(lc->mx, rc->mx);
    }
    LL querymn(int L, int R) {
        push();
        if (l == L && r == R) return mn;
        else if (R <= mid) return lc->querymn(L, R);
        else if (L >= mid + 1) return rc->querymn(L, R);
        else {
            return min(lc->querymn(L, mid), rc->querymn(mid + 1, R));
        }
    }
    LL querymx(int L, int R) {
        push();
        if (l == L && r == R) return mx;
        else if (R <= mid) return lc->querymx(L, R);
        else if (L >= mid + 1) return rc->querymx(L, R);
        else {
            return max(lc->querymx(L, mid), rc->querymx(mid + 1, R));
        }
    }
    //segroot = new segtree(0, n - 1)
};
vl fac, inv, numinv;
inline LL power(LL a, LL p) {
    LL ans = 1;
    while (p) {
        if (p & 1) ans = ans * a % MOD;
        p >>= 1;
        a = a * a % MOD;
    }
    return ans;
}
inline LL ncr(int n, int r) {
    return fac[n] * inv[r] % MOD * inv[n - r] % MOD;
}
inline void calfacinv(int n) {
    fac.reserve(n + 1);
    fac[0] = fac[1] = 1;
    for (int i = 2; i <= n; i++) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    numinv.reserve(n + 1);
    numinv[0] = numinv[1] = 1;
    for (int i = 2; i <= n; i++) {
        numinv[i] = numinv[MOD % i] * (MOD - MOD / i) % MOD;
    }
    inv.reserve(n + 1);
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        inv[i] = numinv[i] * inv[i - 1] % MOD;
    }
    return;
}
struct node {
    int x, y;
    bool operator < (const node &T) const {
        return x < T.x;
    }
};

int T;
int n;
pii a[200005];
int ans[200005];

void solve(int CASE) {
    ri(n);
    segtree *leftseg = new segtree(0, n + 1), *rightseg = new segtree(0, n + 1);
    for (int i = 1; i <= n; i++) {
        ri(a[i].x);
        a[i].y = i;
        leftseg->update(i, n + 1, 1);
        rightseg->update(0, i, 1);
    }
    sort(a + 1, a + n + 1);
    int last = 0, p;
    while (last < n) {
        p = last + 1;
        while (p < n && a[p].x == a[p + 1].x) {
            p++;
        }
        int mn, mx;
        for (int i = last + 1; i <= p; i++) {
            mx = leftseg->querymx(a[i].y - 1, a[i].y - 1) - leftseg->querymn(0, a[i].y - 1);
            mx += rightseg->querymx(a[i].y + 1, a[i].y + 1) - rightseg->querymn(a[i].y + 1, n + 1);
            ans[a[i].y] = (mx + 1) / 2;
        }
        for (int i = last + 1; i <= p; i++) {
            leftseg->update(a[i].y, n + 1, -2);
            rightseg->update(0, a[i].y, -2);
        }
        for (int i = last + 1; i <= p; i++) {
            mn = leftseg->querymn(a[i].y - 1, a[i].y - 1) - leftseg->querymx(0, a[i].y - 1);
            mn += rightseg->querymn(a[i].y + 1, a[i].y + 1) - rightseg->querymx(a[i].y + 1, n + 1);
            ans[a[i].y] = max(ans[a[i].y], -mn / 2);
        }
        last = p;
    }
    for (int i = 1; i <= n; i++) {
        printf(i == n? "%d\n":"%d ", ans[i]);
    }
    return;
}

int main() {
    T = 1;
    // ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    // cin >> T;
    // calfacinv(1e6);
    for (int _ = 1; _ <= T; _++) {
        solve(_);
    }
    return 0;
}