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.
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 7;
int n, s[maxn];
map<int, vector<int>> mp;
struct Node{
    int val1, val2, lazy;
    Node(int val1, int val2, int lazy):val1(val1), val2(val2), lazy(lazy){}
    Node(){}
} tree[maxn << 2];
int head, width;
bool vis[maxn * 2];
int my_left(int pos) {
    return (pos - width) * 2 - 1;
}
int my_right(int pos) {
    return (pos - width) * 2;
}

void make_tree() {
    width = 1;
    while(width < n) width <<= 1;
    for(int i = 1;i <= n; ++i) tree[i].val1 = tree[i].val2 = -1;
    for(int i = 2;i <= width; ++i) tree[i].val1 += tree[i - 1].val1, tree[i].val2 += tree[i - 1].val2;
    for(int i = width + 1;i <= width * 2; ++i) tree[i].val1 = -0x3f3f3f3f, tree[i].val2 = 0x3f3f3f3f;
    head = 1;
    int next = width + 1;
    while(head != next) {
        tree[next].val1 = max(tree[next].val1, tree[head].val1);
        tree[next].val2 = min(tree[next].val2, tree[head].val2);
        head += 1;
        next = (head + 1) / 2 + width;
    }
    head--;
}

void add(int i, int l, int r, int pos) {
    if(l == r) {
        tree[pos].val1 += 2;
        tree[pos].val2 += 2;
        return;
    }
    if(i < l) {
        tree[pos].lazy += 2;
        tree[pos].val1 += 2;
        tree[pos].val2 += 2;
        return;
    }
    int mid = (l + r) >> 1;
    tree[my_left(pos)].lazy += tree[pos].lazy;
    tree[my_left(pos)].val1 += tree[pos].lazy;
    tree[my_left(pos)].val2 += tree[pos].lazy;
    tree[my_right(pos)].lazy += tree[pos].lazy;
    tree[my_right(pos)].val1 += tree[pos].lazy;
    tree[my_right(pos)].val2 += tree[pos].lazy;
    tree[pos].lazy = 0;
    if (i <= mid) {
        add(i, l, mid, my_left(pos));
    }
    add(i, mid + 1, r, my_right(pos));
    tree[pos].val1 = max(tree[my_left(pos)].val1, tree[my_right(pos)].val1);
    tree[pos].val2 = min(tree[my_left(pos)].val2, tree[my_right(pos)].val2);
}

pair<int, int> query(int l, int r, int L, int R, int pos) {
    if(L == R) return pair<int, int>(tree[pos].val1, tree[pos].val2);
    if(l == L && r == R) {
        return pair<int, int>(tree[pos].val1, tree[pos].val2);
    }
    int mid = (L + R) >> 1;
    tree[my_left(pos)].lazy += tree[pos].lazy;
    tree[my_left(pos)].val1 += tree[pos].lazy;
    tree[my_left(pos)].val2 += tree[pos].lazy;
    tree[my_right(pos)].lazy += tree[pos].lazy;
    tree[my_right(pos)].val1 += tree[pos].lazy;
    tree[my_right(pos)].val2 += tree[pos].lazy;
    tree[pos].lazy = 0;
    if(r <= mid) {
        return query(l, r, L, mid, my_left(pos));
    } else if (l > mid){
        return query(l, r, mid + 1, R, my_right(pos));
    } else {
        pair<int, int> lresult = query(l, mid, L, mid, my_left(pos));
        pair<int, int> rresult = query(mid + 1, r, mid + 1, R, my_right(pos));
        /***
        cout<<l<<" "<<r<<endl;
        cout<<L<<" "<<R<<endl;
        cout<<lresult.first<<" "<<lresult.second<<endl;
        cout<<rresult.first<<" "<<rresult.second<<endl;
        cout<<"ggggggg"<<endl;
        ***/
        return pair<int, int>(max(lresult.first, rresult.first), min(lresult.second, rresult.second));
    }
}

int result[maxn];
int main(int argc, char* argv[]) {
    scanf("%d", &n);
    for(int i = 1;i <= n; ++i) {
        scanf("%d", s + i);
        if (mp.find(s[i]) == mp.end()) {
            mp[s[i]] = vector<int>();
        }
        mp[s[i]].push_back(i);
    }
    make_tree();
    sort(s + 1, s + n + 1);
    for(int i = n;i >= 1; --i) {
        if(vis[s[i]]) continue;
        vis[s[i]] = true;
        for(auto j: mp[s[i]]) {
            pair<int, int> ans1(0, 0), ans2(0, 0);
            if (j <= width) ans1 = query(j, width, 1, width, head);
            if (j - 1 >= 1) ans2 = query(1, j - 1, 1, width, head);
            ans2.first = max(ans2.first, 0);
            ans2.second = min(ans2.second, 0);
            int result2 = ans1.second - ans2.first + 1;
            if(result2 < 0) result[j] = max(result[j], (-result2) / 2);

            /**
            if(s[i] == 22) {
            cout<<s[i]<<endl;
            cout<<j<<endl;
            cout<<ans1.first<<endl;
            cout<<ans1.second<<endl;

            cout<<ans2.first<<endl;
            cout<<ans2.second<<endl;
            cout<<result[j]<<endl;
            cout<<"-----------"<<endl;
            }
            **/

        }
        /**
        if(s[i] == 22){
            cout<<"------------"<<endl;
            for(int k = 0;k <= width * 2; ++k) {
                cout<<tree[k].val1<<" ";
            }
            cout<<endl;
            cout<<width<<endl;
            cout<<head<<endl;
            break;
        }
        **/
        for(auto j: mp[s[i]]) {
            add(j, 1, width, head);
        }
        for(auto j: mp[s[i]]) {
            pair<int, int> ans1(0, 0), ans2(0, 0);
            if (j <= width) ans1 = query(j, width, 1, width, head);
            if (j - 1 >= 1) ans2 = query(1, j - 1, 1, width, head);
            ans2.first = max(ans2.first, 0);
            ans2.second = min(ans2.second, 0);
            int result1 = ans1.first - ans2.second - 1;
            if(result1 > 0) result[j] = max(result[j], (result1 + 1) / 2);
        }
    }
    for(int i = 1;i <= n; ++i) {
        printf("%d", result[i]);
        if(i != n) {
            printf(" ");
        } else {
            printf("\n");
        }
    }
    return 0;
}

/***
Input
5
5 4 3 2 1
Output
2 1 1 2 2
***/

/***
1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
1  0  1  2  1  2  1  0  1  2  1  2  3  4  3  2  3  4  3  2  3  2  3  4  5  4  5  6  5  4  3  2  3  4  3  4  5  6  5  6  7  6  5  4  5  4  3  4  5  6
47 3  42 46 3  48 11 21 46 37 9  49 46 25 22 10 42 46 21 22 50 10 41 43 41 10 46 41 10 4  19 5  37 46 10 46 48 41 19 32 43 17 19 4  23 10 10 42 47 42
20 24 10 19 24 22 12 6  19 4  20 23 19 3  4  13 10 19 6  4  24 13 8  12 8  13 19 8  13 22 8  21 4  19 13 19 22 8  8  3  12 11 8  22 3  13 13 10 20 10
20 25 10 19 25 22 12 7  19 4  20 23 19 3  5  19 10 19 7  5  24 19 8  12 8  19 19 8  19 23 10 21 4  19 19 19 22 8  10 3  12 11 10 23 3  19 19 10 20 10

***/
