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.
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif


const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; 
const ll identity = 0;
const ll SZ = 262144;


struct Seg1 {

ll sum[2*SZ], lazy[2*SZ];

ll combine(ll A, ll B) {
    return min(A, B);
}

ll combineUpd(ll A, ll B) {
    return A+B;
}

void push(int index, ll L, ll R) {
    sum[index] = combineUpd(sum[index], lazy[index]);
    if (L != R) lazy[2*index] = combineUpd(lazy[2*index], lazy[index]), lazy[2*index+1] = combineUpd(lazy[2*index+1], lazy[index]);
    lazy[index] = identity;
}

void pull(int index) {
    sum[index] = combine(sum[2*index], sum[2*index+1]);
}

ll query(int lo, int hi, int index = 1, ll L = 0, ll R = SZ-1) {
    push(index, L, R);
    if (lo > R || L > hi) return SZ;
    if (lo <= L && R <= hi) return sum[index];

    int M = (L+R) / 2;
    return combine(query(lo, hi, 2*index, L, M), query(lo, hi, 2*index+1, M+1, R));
}

void update(int lo, int hi, ll increase, int index = 1, ll L = 0, ll R = SZ-1) {
    push(index, L, R);
    if (hi < L || R < lo) return;
    if (lo <= L && R <= hi) {
        lazy[index] = increase;
        push(index, L, R);
        return;
    }

    int M = (L+R) / 2;
    update(lo, hi, increase, 2*index, L, M); update(lo, hi, increase, 2*index+1, M+1, R);
    pull(index);
}
};

struct Seg2 {

ll sum[2*SZ], lazy[2*SZ];

ll combine(ll A, ll B) {
    return max(A, B);
}

ll combineUpd(ll A, ll B) {
    return A+B;
}

void push(int index, ll L, ll R) {
    sum[index] = combineUpd(sum[index], lazy[index]);
    if (L != R) lazy[2*index] = combineUpd(lazy[2*index], lazy[index]), lazy[2*index+1] = combineUpd(lazy[2*index+1], lazy[index]);
    lazy[index] = identity;
}

void pull(int index) {
    sum[index] = combine(sum[2*index], sum[2*index+1]);
}

ll query(int lo, int hi, int index = 1, ll L = 0, ll R = SZ-1) {
    push(index, L, R);
    if (lo > R || L > hi) return -2*SZ;
    if (lo <= L && R <= hi) return sum[index];

    int M = (L+R) / 2;
    return combine(query(lo, hi, 2*index, L, M), query(lo, hi, 2*index+1, M+1, R));
}

void update(int lo, int hi, ll increase, int index = 1, ll L = 0, ll R = SZ-1) {
    push(index, L, R);
    if (hi < L || R < lo) return;
    if (lo <= L && R <= hi) {
        lazy[index] = increase;
        push(index, L, R);
        return;
    }

    int M = (L+R) / 2;
    update(lo, hi, increase, 2*index, L, M); update(lo, hi, increase, 2*index+1, M+1, R);
    pull(index);
}
};

Seg1 seg1;
Seg2 seg2;

void upd(int p, int v) {
    seg1.update(p+1, SZ-1, v);
    seg2.update(p+1, SZ-1, v);
}

int get(int p) {
    ll v = seg2.query(p+1, SZ-1) - seg1.query(0, p); // p+1?
    //dbg(p, seg2.query(p+1,SZ-1), seg1.query(0, p));
    //v = 0: 0
    //v = 1: 1
    //v = 2: a b c 1
    //v = 3: a b c d 2
    return v;
}


void solve() {
    int N; cin >> N;
    vi pos[N+1];
    F0R(i, N) {
        int X; cin >> X; pos[X].pb(i);
    }
    F0R(i, N) upd(i, 1);

    int ans[N];
    F0R(i, N+1) {
        trav(a, pos[i]) {
            upd(a, -1);
            ans[a] = (get(a)+1)/2;
            upd(a, 1);
        }
        trav(a, pos[i]) {
            upd(a, -2);
        }
    }

    F0R(i, N) upd(i, 2);

    F0Rd(i, N+1) {
        trav(a, pos[i]) {
            upd(a, -1);
            ckmax(ans[a], get(a)/2);
            upd(a, 1);
        }
        trav(a, pos[i]) upd(a, -2);
    }

    F0R(i, N) {
        cout << ans[i] << " ";
    }
    cout << nl;

}
 
int main() {
    cin.tie(0)->sync_with_stdio(0); 
    cin.exceptions(cin.failbit);

    int T = 1;
//    cin >> T;
    while(T--) {
        solve();
    }

	return 0;
}


