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<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
//using std::cout;
//using std::endl;
using std::sort;
using std::min;
using std::max;
#define int long long

long long read(){//int 无负数 
	long long h=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')h=(h<<1)+(h<<3)+c-'0',c=getchar();
	return h;
}

const int MAXN=800800;
int a[MAXN];
pair<int,int>s[MAXN];
int ans[MAXN];

struct Segment_Tree{
	#define Root 1,n,1
	#define Lson l,mid,rt<<1
	#define Rson mid+1,r,rt<<1|1 
	#define Ls rt<<1
	#define Rs rt<<1|1
	int mx[MAXN],mn[MAXN];
	int col[MAXN];//区间加 
	Segment_Tree(){
		memset(mx,0,sizeof(mx));
		memset(mn,0x3f,sizeof(mn));
	}
	
	void build(int l,int r,int rt,int tp){//1是奇数，0是偶数 
		col[rt]=0;
		if(l==r){
			if(tp==1){
				if(l&1)mn[rt]=mx[rt]=(l>>1);//奇数 
				else mn[rt]=0x3f3f3f3f,mx[rt]=-0x3f3f3f3f; 
			}
			if(tp==0){
				if(!(l&1))mn[rt]=mx[rt]=(l>>1);//偶数
				else mn[rt]=0x3f3f3f3f,mx[rt]=-0x3f3f3f3f; 
			}
			return; 
		}
		int mid=(l+r)>>1;
		build(Lson,tp),build(Rson,tp);
		mn[rt]=min(mn[Ls],mn[Rs]);
		mx[rt]=max(mx[Ls],mx[Rs]);
//		cout<<"BUILD"<<l<<' '<<r<<" "<<mn[rt]<<' '<<mx[rt]<<endl;
	}
	
	void color(int rt,int A){
		mn[rt]+=A,mx[rt]+=A,col[rt]+=A;
	}
	
	void push_down(int rt){
		color(Ls,col[rt]);
		color(Rs,col[rt]);
		col[rt]=0;
	}
	
	void modify(int l,int r,int rt,int nowl,int nowr,int A){
		if(nowl<=l&&r<=nowr){
			color(rt,A);
//		cout<<l<<' '<<r<<' '<<mn[rt]<<' '<<mx[rt]<<endl;
		return void();
		}
		if(col[rt])push_down(rt);
		int mid=(l+r)>>1;
		if(nowl<=mid)modify(Lson,nowl,nowr,A);
		if(nowr>mid)modify(Rson,nowl,nowr,A);
		mn[rt]=min(mn[Ls],mn[Rs]);
		mx[rt]=max(mx[Ls],mx[Rs]);
//		cout<<l<<' '<<r<<' '<<mn[rt]<<' '<<mx[rt]<<endl;
	}
	
	int query_mn(int l,int r,int rt,int nowl,int nowr){
		if(nowl<=l&&r<=nowr)return mn[rt];
		if(col[rt])push_down(rt);
		int mid=(l+r)>>1;
		if(nowl<=mid) {
			if(nowr>mid)return min(query_mn(Lson,nowl,nowr),query_mn(Rson,nowl,nowr));
			return query_mn(Lson,nowl,nowr);
		}return query_mn(Rson,nowl,nowr);
	}
	
	int query_mx(int l,int r,int rt,int nowl,int nowr){
		if(nowl<=l&&r<=nowr)return mx[rt];
		if(col[rt])push_down(rt);
		int mid=(l+r)>>1;
		if(nowl<=mid){
			if(nowr>mid)return max(query_mx(Lson,nowl,nowr),query_mx(Rson,nowl,nowr));
			return query_mx(Lson,nowl,nowr);
		}return query_mx(Rson,nowl,nowr);
	}
}t[2];
int Ans[MAXN];

signed main(){
	int n=read(); 
	for(int i=1;i<=n;i++){
		a[i]=read();
		s[i].first=a[i],s[i].second=i;
	}
	sort(s+1,s+n+1);
	
	t[1].build(Root,1),t[0].build(Root,0);
	int lst=0; //上个同色段的结束 
	for(int i=1;i<=n;i++){
		if(i!=1&&s[i].first!=s[i-1].first){//颜色不同了 
			for(int w=lst+1;w<=i-1;w++){
//				cout<<"WW"<<w<<endl;
				t[0].modify(Root,s[w].second,n,-1);
				t[1].modify(Root,s[w].second,n,-1);
			}
			lst=i-1;
		}
//		int mx=0;
		int x=s[i].second;
		for(int wr=0;wr<=1;wr++){
			for(int wl=0;wl<=1;wl++){
				long long ansR=t[wr].query_mx(Root,x,n);
				long long ansL=(x!=1?t[wl^1].query_mn(Root,1,x-1):0);if(wl&1)ansL=min(ansL,0ll);//至少有啥也不选 
				long long anss=ansR-ansL+1;
				if(wr==0&&wl==0)anss--;
				if(i==2&&wr==0&&wl==1){
//					cout<<ansL<<' '<<ansR<<endl; 
				} 
				Ans[x]=max(Ans[x],anss-1);
			}
		}
	}
//	for(int i=1;i<=n;i++)cout<<Ans[i]<<' ';puts("");
	
	
	for(int i=1;i<=n;i++)s[i].first=-s[i].first;
	sort(s+1,s+n+1);
	
	t[1].build(Root,1),t[0].build(Root,0);
	lst=0; //上个同色段的结束 
	for(int i=1;i<=n;i++){
		if(i!=1&&s[i].first!=s[i-1].first){//颜色不同了 
			for(int w=lst+1;w<=i-1;w++){
				t[0].modify(Root,s[w].second,n,-1);
				t[1].modify(Root,s[w].second,n,-1);
			}
			lst=i-1;
		}
//		int mx=0;
		int x=s[i].second;
		for(int wr=0;wr<=1;wr++){
			for(int wl=0;wl<=1;wl++){
				long long ansR=t[wr].query_mx(Root,x,n);
				long long ansL=(x!=1?t[wl^1].query_mn(Root,1,x-1):0);if(wl&1)ansL=min(ansL,0ll);//至少有啥也不选 
				long long anss=ansR-ansL+1;
				if(wr==0&&wl==0)anss--;
				if(wr^wl){//长为偶数，需要调整一下中心点 
					anss--;
				}
				if(i==2){
//					cout<<"??"<<ansL<<' '<<ansR<<' '<<anss<<endl;
				}
				Ans[x]=max(Ans[x],anss-1);
			}
		}
	}
	for(int i=1;i<=n;i++)std::cout<<Ans[i]<<' ';puts("");
	return 0;
}