#include <bits/stdc++.h>

using namespace std;

// #define CODEJAM

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;

#define REP(k, n) for (ll k = 0; k < (ll)(n); ++k)
#define REPREV(k, n) for (ll k = (ll)(n)-1; k >= 0; --k)
#define FOR(k, a, b) for (ll k = (ll)(a); k < (ll)(b); ++k)
#define FORREV(k, a, b) for (ll k = (ll)(b)-1; k >= (ll)(a); --k)
#define FOREACH(e, v) for (auto& e : v)

#define TGET(t, i) get<i>(t)
#define TSET(t, i, a) get<i>(t) = a
// MinHeap - priority_queue<ll, vll, greater<ll>> pq;

#define EVEN(n) ((n)&1) == 0
#define ODD(n) ((n)&1) == 1

#ifdef DEBUG
#define endl endl
#else
#define endl "\n"
#endif

#define SORT(v) sort(v.begin(), v.end())
#define SORTREV(v) sort(v.rbegin(), v.rend())
#define SHUFFLE(v) random_shuffle(v.begin(), v.end())
//srand(unsigned(time(0)));

#define REMOVEAT(v, i) v.erase(v.begin() + i)
#define REVERSE(v) reverse(v.begin(), v.end())
#define UNIQUE(v) \
    SORT(v);      \
    v.resize(distance(v.begin(), unique(v.begin(), v.end())))

ostream& operator<<(ostream& str, const pll& p) {
    str << p.first << " " << p.second;
    return str;
}

template <typename T>
void join(T& arr, string sep) {
    bool first = true;
    for (auto t : arr) {
        if (first) {
            first = false;
            cout << t;
        } else {
            cout << sep << t;
        }
    }
    cout << endl;
}

const ll md = 1e9 + 7;
ll MOD(ll x) {
    ll r = x % md;
    if (r < 0) {
        r += md;
    }
    return r;
}

#define POS "POSSIBLE"
#define IMPOS "IMPOSSIBLE"

// #define INF DBL_MAX
// #define INF LLONG_MAX
// #define MINF LLONG_MIN
#define INF 1e18
#define MINF -INF

template <typename num_t>
struct segtree {
    int n, depth;
    vector<num_t> tree, lazy;

    void init(int s, vll& arr) {
        n = s;
        tree = vector<num_t>(4 * s, 0);
        lazy = vector<num_t>(4 * s, 0);
        init(0, 0, n - 1, arr);
    }

    num_t init(int i, int l, int r, vll& arr) {
        if (l == r) return tree[i] = arr[l];

        int mid = (l + r) / 2;
        num_t a = init(2 * i + 1, l, mid, arr),
              b = init(2 * i + 2, mid + 1, r, arr);
        return tree[i] = a.op(b);
    }

    void update(int l, int r, num_t v) {
        if (l > r) return;
        update(0, 0, n - 1, l, r, v);
    }

    num_t update(int i, int tl, int tr, int ql, int qr, num_t v) {
        eval_lazy(i, tl, tr);

        if (tr < ql || qr < tl) return tree[i];
        if (ql <= tl && tr <= qr) {
            lazy[i] = lazy[i].val + v.val;
            eval_lazy(i, tl, tr);
            return tree[i];
        }

        int mid = (tl + tr) / 2;
        num_t a = update(2 * i + 1, tl, mid, ql, qr, v),
              b = update(2 * i + 2, mid + 1, tr, ql, qr, v);
        return tree[i] = a.op(b);
    }

    num_t query(int l, int r) {
        if (l > r) return num_t::null_v;
        return query(0, 0, n - 1, l, r);
    }

    num_t query(int i, int tl, int tr, int ql, int qr) {
        eval_lazy(i, tl, tr);

        if (ql <= tl && tr <= qr) return tree[i];
        if (tr < ql || qr < tl) return num_t::null_v;

        int mid = (tl + tr) / 2;
        num_t a = query(2 * i + 1, tl, mid, ql, qr),
              b = query(2 * i + 2, mid + 1, tr, ql, qr);
        return a.op(b);
    }

    void eval_lazy(int i, int l, int r) {
        tree[i] = tree[i].lazy_op(lazy[i], (r - l + 1));
        if (l != r) {
            lazy[i * 2 + 1] = lazy[i].val + lazy[i * 2 + 1].val;
            lazy[i * 2 + 2] = lazy[i].val + lazy[i * 2 + 2].val;
        }

        lazy[i] = num_t();
    }
};

struct max_t {
    long long val;
    static const long long null_v = -9223372036854775807LL;

    max_t() : val(0) {}
    max_t(long long v) : val(v) {}

    max_t op(max_t& other) {
        return max_t(max(val, other.val));
    }

    max_t lazy_op(max_t& v, int size) {
        return max_t(val + v.val);
    }
};

struct min_t {
    long long val;
    static const long long null_v = 9223372036854775807LL;

    min_t() : val(0) {}
    min_t(long long v) : val(v) {}

    min_t op(min_t& other) {
        return min_t(min(val, other.val));
    }

    min_t lazy_op(min_t& v, int size) {
        return min_t(val + v.val);
    }
};

void solve() {
    ll n;
    cin >> n;
    vll res(n);
    vll a(n);

    vll b(n + 1);
    // val to the right of median
    segtree<max_t> stMx1;
    stMx1.init(n + 1, b);
    segtree<min_t> stMn1;
    stMn1.init(n + 1, b);

    segtree<max_t> stMx2;
    stMx2.init(n + 1, b);
    segtree<min_t> stMn2;
    stMn2.init(n + 1, b);

    REP(i, n) {
        cin >> a[i];
        a[i]--;
        stMx1.update(0, i, -1);
        stMn1.update(0, i, -1);

        stMx2.update(0, i, +1);
        stMn2.update(0, i, +1);
    }

    vll idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](ll i, ll j) {
        if (a[i] == a[j]) {
            return i < j;
        }

        return a[i] < a[j];
    });

    for (int ii = 0; ii < n; ii++) {
        int i = idx[ii];
        stMx1.update(0, i, +2);
        stMn1.update(0, i, +2);

        if (ii + 1 == n || a[i] != a[idx[ii + 1]]) {
            int jj = ii;
            while (jj >= 0 && a[idx[jj]] == a[i]) {
                int j = idx[jj];
                ll sm = 0;

                if (j + 1 < n) {
                    ll cand = stMn1.query(j + 2, n).val;
                    cand = stMn1.query(j + 1, j + 1).val - cand;
                    sm += max(0ll, cand);
                }

                if (j - 1 >= 0) {
                    ll cand = stMx1.query(0, j - 1).val;
                    cand = cand - stMx1.query(j, j).val;
                    sm += max(0ll, cand);
                }

                res[j] = max(res[j], sm / 2);
                jj--;
            }
        }
    }

    for (int ii = 0; ii < n; ii++) {
        int i = idx[ii];
        if (ii + 1 == n || a[i] != a[idx[ii + 1]]) {
            int r = ii;
            int l = ii;

            int jj = ii;
            while (jj >= 0 && a[idx[jj]] == a[i]) {
                int j = idx[jj];
                l = jj;
                ll sm = 0;

                if (j + 1 < n) {
                    ll cand = stMn2.query(j + 2, n).val;
                    cand = stMn2.query(j + 1, j + 1).val - cand;
                    sm += max(0ll, cand);
                }

                if (j - 1 >= 0) {
                    ll cand = stMx2.query(0, j - 1).val;
                    cand = cand - stMx2.query(j, j).val;
                    sm += max(0ll, cand);
                }

                res[j] = max(res[j], (sm + 1) / 2);
                jj--;
            }

            for (int kk = l; kk <= r; kk++) {
                int iii = idx[kk];
                stMx2.update(0, iii, -2);
                stMn2.update(0, iii, -2);
            }
        }
    }

    join(res, " ");
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt = 1;
// cin >> tt;
#ifdef CODEJAM
    cin >> tt;
#endif

#ifdef DEBUG
    for (int t = 1; t <= tt || cin.rdbuf()->in_avail(); t++) {
        // cout << "Case #" << t << ": ";
        solve();
    }

//     for (int t = 1; t <= tt; t++) {
// // cout << "Case #" << t << ": ";
// #ifdef CODEJAM
//         cout << "Case #" << t << ": ";
// #endif
//         solve();
//     }
#else
    for (int t = 1; t <= tt; t++) {
// cout << "Case #" << t << ": ";
#ifdef CODEJAM
        cout << "Case #" << t << ": ";
#endif
        solve();
    }
#endif

    return 0;
}
### Prompt

Create a solution in CPP for the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

// #define CODEJAM

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;

#define REP(k, n) for (ll k = 0; k < (ll)(n); ++k)
#define REPREV(k, n) for (ll k = (ll)(n)-1; k >= 0; --k)
#define FOR(k, a, b) for (ll k = (ll)(a); k < (ll)(b); ++k)
#define FORREV(k, a, b) for (ll k = (ll)(b)-1; k >= (ll)(a); --k)
#define FOREACH(e, v) for (auto& e : v)

#define TGET(t, i) get<i>(t)
#define TSET(t, i, a) get<i>(t) = a
// MinHeap - priority_queue<ll, vll, greater<ll>> pq;

#define EVEN(n) ((n)&1) == 0
#define ODD(n) ((n)&1) == 1

#ifdef DEBUG
#define endl endl
#else
#define endl "\n"
#endif

#define SORT(v) sort(v.begin(), v.end())
#define SORTREV(v) sort(v.rbegin(), v.rend())
#define SHUFFLE(v) random_shuffle(v.begin(), v.end())
//srand(unsigned(time(0)));

#define REMOVEAT(v, i) v.erase(v.begin() + i)
#define REVERSE(v) reverse(v.begin(), v.end())
#define UNIQUE(v) \
    SORT(v);      \
    v.resize(distance(v.begin(), unique(v.begin(), v.end())))

ostream& operator<<(ostream& str, const pll& p) {
    str << p.first << " " << p.second;
    return str;
}

template <typename T>
void join(T& arr, string sep) {
    bool first = true;
    for (auto t : arr) {
        if (first) {
            first = false;
            cout << t;
        } else {
            cout << sep << t;
        }
    }
    cout << endl;
}

const ll md = 1e9 + 7;
ll MOD(ll x) {
    ll r = x % md;
    if (r < 0) {
        r += md;
    }
    return r;
}

#define POS "POSSIBLE"
#define IMPOS "IMPOSSIBLE"

// #define INF DBL_MAX
// #define INF LLONG_MAX
// #define MINF LLONG_MIN
#define INF 1e18
#define MINF -INF

template <typename num_t>
struct segtree {
    int n, depth;
    vector<num_t> tree, lazy;

    void init(int s, vll& arr) {
        n = s;
        tree = vector<num_t>(4 * s, 0);
        lazy = vector<num_t>(4 * s, 0);
        init(0, 0, n - 1, arr);
    }

    num_t init(int i, int l, int r, vll& arr) {
        if (l == r) return tree[i] = arr[l];

        int mid = (l + r) / 2;
        num_t a = init(2 * i + 1, l, mid, arr),
              b = init(2 * i + 2, mid + 1, r, arr);
        return tree[i] = a.op(b);
    }

    void update(int l, int r, num_t v) {
        if (l > r) return;
        update(0, 0, n - 1, l, r, v);
    }

    num_t update(int i, int tl, int tr, int ql, int qr, num_t v) {
        eval_lazy(i, tl, tr);

        if (tr < ql || qr < tl) return tree[i];
        if (ql <= tl && tr <= qr) {
            lazy[i] = lazy[i].val + v.val;
            eval_lazy(i, tl, tr);
            return tree[i];
        }

        int mid = (tl + tr) / 2;
        num_t a = update(2 * i + 1, tl, mid, ql, qr, v),
              b = update(2 * i + 2, mid + 1, tr, ql, qr, v);
        return tree[i] = a.op(b);
    }

    num_t query(int l, int r) {
        if (l > r) return num_t::null_v;
        return query(0, 0, n - 1, l, r);
    }

    num_t query(int i, int tl, int tr, int ql, int qr) {
        eval_lazy(i, tl, tr);

        if (ql <= tl && tr <= qr) return tree[i];
        if (tr < ql || qr < tl) return num_t::null_v;

        int mid = (tl + tr) / 2;
        num_t a = query(2 * i + 1, tl, mid, ql, qr),
              b = query(2 * i + 2, mid + 1, tr, ql, qr);
        return a.op(b);
    }

    void eval_lazy(int i, int l, int r) {
        tree[i] = tree[i].lazy_op(lazy[i], (r - l + 1));
        if (l != r) {
            lazy[i * 2 + 1] = lazy[i].val + lazy[i * 2 + 1].val;
            lazy[i * 2 + 2] = lazy[i].val + lazy[i * 2 + 2].val;
        }

        lazy[i] = num_t();
    }
};

struct max_t {
    long long val;
    static const long long null_v = -9223372036854775807LL;

    max_t() : val(0) {}
    max_t(long long v) : val(v) {}

    max_t op(max_t& other) {
        return max_t(max(val, other.val));
    }

    max_t lazy_op(max_t& v, int size) {
        return max_t(val + v.val);
    }
};

struct min_t {
    long long val;
    static const long long null_v = 9223372036854775807LL;

    min_t() : val(0) {}
    min_t(long long v) : val(v) {}

    min_t op(min_t& other) {
        return min_t(min(val, other.val));
    }

    min_t lazy_op(min_t& v, int size) {
        return min_t(val + v.val);
    }
};

void solve() {
    ll n;
    cin >> n;
    vll res(n);
    vll a(n);

    vll b(n + 1);
    // val to the right of median
    segtree<max_t> stMx1;
    stMx1.init(n + 1, b);
    segtree<min_t> stMn1;
    stMn1.init(n + 1, b);

    segtree<max_t> stMx2;
    stMx2.init(n + 1, b);
    segtree<min_t> stMn2;
    stMn2.init(n + 1, b);

    REP(i, n) {
        cin >> a[i];
        a[i]--;
        stMx1.update(0, i, -1);
        stMn1.update(0, i, -1);

        stMx2.update(0, i, +1);
        stMn2.update(0, i, +1);
    }

    vll idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](ll i, ll j) {
        if (a[i] == a[j]) {
            return i < j;
        }

        return a[i] < a[j];
    });

    for (int ii = 0; ii < n; ii++) {
        int i = idx[ii];
        stMx1.update(0, i, +2);
        stMn1.update(0, i, +2);

        if (ii + 1 == n || a[i] != a[idx[ii + 1]]) {
            int jj = ii;
            while (jj >= 0 && a[idx[jj]] == a[i]) {
                int j = idx[jj];
                ll sm = 0;

                if (j + 1 < n) {
                    ll cand = stMn1.query(j + 2, n).val;
                    cand = stMn1.query(j + 1, j + 1).val - cand;
                    sm += max(0ll, cand);
                }

                if (j - 1 >= 0) {
                    ll cand = stMx1.query(0, j - 1).val;
                    cand = cand - stMx1.query(j, j).val;
                    sm += max(0ll, cand);
                }

                res[j] = max(res[j], sm / 2);
                jj--;
            }
        }
    }

    for (int ii = 0; ii < n; ii++) {
        int i = idx[ii];
        if (ii + 1 == n || a[i] != a[idx[ii + 1]]) {
            int r = ii;
            int l = ii;

            int jj = ii;
            while (jj >= 0 && a[idx[jj]] == a[i]) {
                int j = idx[jj];
                l = jj;
                ll sm = 0;

                if (j + 1 < n) {
                    ll cand = stMn2.query(j + 2, n).val;
                    cand = stMn2.query(j + 1, j + 1).val - cand;
                    sm += max(0ll, cand);
                }

                if (j - 1 >= 0) {
                    ll cand = stMx2.query(0, j - 1).val;
                    cand = cand - stMx2.query(j, j).val;
                    sm += max(0ll, cand);
                }

                res[j] = max(res[j], (sm + 1) / 2);
                jj--;
            }

            for (int kk = l; kk <= r; kk++) {
                int iii = idx[kk];
                stMx2.update(0, iii, -2);
                stMn2.update(0, iii, -2);
            }
        }
    }

    join(res, " ");
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt = 1;
// cin >> tt;
#ifdef CODEJAM
    cin >> tt;
#endif

#ifdef DEBUG
    for (int t = 1; t <= tt || cin.rdbuf()->in_avail(); t++) {
        // cout << "Case #" << t << ": ";
        solve();
    }

//     for (int t = 1; t <= tt; t++) {
// // cout << "Case #" << t << ": ";
// #ifdef CODEJAM
//         cout << "Case #" << t << ": ";
// #endif
//         solve();
//     }
#else
    for (int t = 1; t <= tt; t++) {
// cout << "Case #" << t << ": ";
#ifdef CODEJAM
        cout << "Case #" << t << ": ";
#endif
        solve();
    }
#endif

    return 0;
}
```