#include <bits/stdc++.h>
using namespace std;

#define Int register int
#define INF 0x7f7f7f7f
#define ll long long
#define MAXN 200005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,a[MAXN],sz[MAXN][2],sf[MAXN][2];

struct ExSegment_Tree{
	int maxv[MAXN << 2],minv[MAXN << 2],seca[MAXN << 2],seci[MAXN << 2],cnta[MAXN << 2],cnti[MAXN << 2],tagv[MAXN << 2];
	ll sumv[MAXN << 2];
	void Pushup (int i){
		int l = i << 1,r = i << 1 | 1;sumv[i] = sumv[l] + sumv[r];
		if (maxv[l] == maxv[r]) maxv[i] = maxv[l],cnta[i] = cnta[l] + cnta[r],seca[i] = max (seca[l],seca[r]);
		else{
			if (maxv[l] > maxv[r]) swap (l,r);
			maxv[i] = maxv[r];
			cnta[i] = cnta[r];
			seca[i] = max (maxv[l],seca[r]);
		}
		if (minv[l] == minv [r]) minv[i] = minv[l],cnti[i] = cnti[l] + cnti[r],seci[i] = min (seci[l],seci[r]);
		else{
			if (minv[l] < minv[r]) swap (l,r);
			minv[i] = minv[r];
			cnti[i] = cnti[r];
			seci[i] = min (minv[l],seci[r]);
		} 
	}
	void AddTag (int i,int l,int r,int v){
		tagv[i] += v;sumv[i] += 1ll * (r - l + 1) * v;
		minv[i] += v,maxv[i] += v,seca[i] += v,seci[i] += v;
	}
	void MaxTag (int i,int l,int r,int v){
		sumv[i] += 1ll * cnti[i] * (v - minv[i]);
		minv[i] = v;maxv[i] = max (v,maxv[i]);
		if (minv[i] == maxv[i]) cnta[i] = cnti[i] = r - l + 1,seca[i] = -INF,seci[i] = INF;
		else seca[i] = max (v,seca[i]);
	}
	void MinTag (int i,int l,int r,int v){
		sumv[i] -= 1ll * cnta[i] * (maxv[i] - v);
		maxv[i] = v;minv[i] = min (minv[i],v);
		if (minv[i] == maxv[i]) cnta[i] = cnti[i] = r - l + 1,seca[i] = -INF,seci[i] = INF;
		else seci[i] = min (seci[i],v);
	}
	void Pushdown (int i,int l,int r){
		int mid = (l + r) >> 1,lson = i << 1,rson = i << 1 | 1;
		if (tagv[i]) AddTag (lson,l,mid,tagv[i]),AddTag (rson,mid + 1,r,tagv[i]),tagv[i] = 0;
		if (maxv[lson] > maxv[i] && seca[lson] < maxv[i]) MinTag (lson,l,mid,maxv[i]);
		if (maxv[rson] > maxv[i] && seca[rson] < maxv[i]) MinTag (rson,mid + 1,r,maxv[i]);
		if (minv[lson] < minv[i] && seci[lson] > minv[i]) MaxTag (lson,l,mid,minv[i]);
		if (minv[rson] < minv[i] && seci[rson] > minv[i]) MaxTag (rson,mid + 1,r,minv[i]);
	}
	void build (int i,int l,int r){
		if (l == r){
			int x = 0;
			sumv[i] = maxv[i] = minv[i] = x,cnta[i] = cnti[i] = 1,seca[i] = -INF,seci[i] = INF;
			return ;
		}
		int mid = (l + r) >> 1;
		build (i << 1,l,mid);
		build (i << 1 | 1,mid + 1,r);
		Pushup (i);
	}
	void ChangeMax (int i,int l,int r,int tl,int tr,int v){
		if (minv[i] >= v) return ;
		if (l >= tl && r <= tr && v < seci[i]) return MaxTag (i,l,r,v);
		int mid = (l + r) >> 1;Pushdown (i,l,r);
		if (tl <= mid) ChangeMax (i << 1,l,mid,tl,tr,v);
		if (tr > mid) ChangeMax (i << 1 | 1,mid + 1,r,tl,tr,v);
		Pushup (i);
	}
	void ChangeSum (int i,int l,int r,int tl,int tr,int v){
		if (tl > tr) return ;
		if (l >= tl && r <= tr) return AddTag (i,l,r,v);
		int mid = (l + r) >> 1;Pushdown (i,l,r);
		if (tl <= mid) ChangeSum (i << 1,l,mid,tl,tr,v);
		if (tr > mid) ChangeSum (i << 1 | 1,mid + 1,r,tl,tr,v);
		Pushup (i);
	} 
	int QueryMax (int i,int l,int r,int tl,int tr){
		if (l >= tl && r <= tr) return maxv[i];
		int mid = (l + r) >> 1;Pushdown (i,l,r);int ans = -INF;
		if (tl <= mid) ans = max (ans,QueryMax (i << 1,l,mid,tl,tr));
		if (tr > mid) ans = max (ans,QueryMax (i << 1 | 1,mid + 1,r,tl,tr));
		return ans;
	}
}Tree; 

signed main(){
	read (n);
	for (Int i = 1;i <= n;++ i) read (a[i]);
	Tree.build (1,1,n);
	for (Int i = 1;i <= n;++ i)
		Tree.ChangeSum (1,1,n,a[i],n,1),
		Tree.ChangeSum (1,1,n,1,a[i] - 1,-1),
		Tree.ChangeMax (1,1,n,1,n,0),sz[i][0] = Tree.QueryMax (1,1,n,a[i],a[i]);
	Tree.build (1,1,n);
	for (Int i = 1;i <= n;++ i)
		Tree.ChangeSum (1,1,n,1,a[i],1),
		Tree.ChangeSum (1,1,n,a[i] + 1,n,-1),
		Tree.ChangeMax (1,1,n,1,n,0),sz[i][1] = Tree.QueryMax (1,1,n,a[i],a[i]);
	Tree.build (1,1,n);
	for (Int i = n;i >= 1;-- i)
		Tree.ChangeSum (1,1,n,a[i],n,1),
		Tree.ChangeSum (1,1,n,1,a[i] - 1,-1),
		Tree.ChangeMax (1,1,n,1,n,0),sf[i][0] = Tree.QueryMax (1,1,n,a[i],a[i]);
	Tree.build (1,1,n);
	for (Int i = n;i >= 1;-- i)
		Tree.ChangeSum (1,1,n,1,a[i],1),
		Tree.ChangeSum (1,1,n,a[i] + 1,n,-1),
		Tree.ChangeMax (1,1,n,1,n,0),sf[i][1] = Tree.QueryMax (1,1,n,a[i],a[i]);
    for (Int i = 1;i <= n;++ i){
		int h1 = (sz[i][0] + sf[i][0] - 1 - 1) / 2,h2 = (sz[i][1] + sf[i][1] - 1) / 2;
		write (max (max (h1,h2),0)),putchar (' ');
	}
	putchar ('\n');
	return 0;
}
/*
第i棵线段树维护数字x后缀<=x的个数->x的最大值
显然在加入a[i]之后>=a[i]的数字都会+1，<a[i]的都会减一
然后每时每刻都需要与0取较大值

似乎是一个吉司机线段树 

然后
*/
### Prompt

Please formulate a cpp solution to 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 Int register int
#define INF 0x7f7f7f7f
#define ll long long
#define MAXN 200005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,a[MAXN],sz[MAXN][2],sf[MAXN][2];

struct ExSegment_Tree{
	int maxv[MAXN << 2],minv[MAXN << 2],seca[MAXN << 2],seci[MAXN << 2],cnta[MAXN << 2],cnti[MAXN << 2],tagv[MAXN << 2];
	ll sumv[MAXN << 2];
	void Pushup (int i){
		int l = i << 1,r = i << 1 | 1;sumv[i] = sumv[l] + sumv[r];
		if (maxv[l] == maxv[r]) maxv[i] = maxv[l],cnta[i] = cnta[l] + cnta[r],seca[i] = max (seca[l],seca[r]);
		else{
			if (maxv[l] > maxv[r]) swap (l,r);
			maxv[i] = maxv[r];
			cnta[i] = cnta[r];
			seca[i] = max (maxv[l],seca[r]);
		}
		if (minv[l] == minv [r]) minv[i] = minv[l],cnti[i] = cnti[l] + cnti[r],seci[i] = min (seci[l],seci[r]);
		else{
			if (minv[l] < minv[r]) swap (l,r);
			minv[i] = minv[r];
			cnti[i] = cnti[r];
			seci[i] = min (minv[l],seci[r]);
		} 
	}
	void AddTag (int i,int l,int r,int v){
		tagv[i] += v;sumv[i] += 1ll * (r - l + 1) * v;
		minv[i] += v,maxv[i] += v,seca[i] += v,seci[i] += v;
	}
	void MaxTag (int i,int l,int r,int v){
		sumv[i] += 1ll * cnti[i] * (v - minv[i]);
		minv[i] = v;maxv[i] = max (v,maxv[i]);
		if (minv[i] == maxv[i]) cnta[i] = cnti[i] = r - l + 1,seca[i] = -INF,seci[i] = INF;
		else seca[i] = max (v,seca[i]);
	}
	void MinTag (int i,int l,int r,int v){
		sumv[i] -= 1ll * cnta[i] * (maxv[i] - v);
		maxv[i] = v;minv[i] = min (minv[i],v);
		if (minv[i] == maxv[i]) cnta[i] = cnti[i] = r - l + 1,seca[i] = -INF,seci[i] = INF;
		else seci[i] = min (seci[i],v);
	}
	void Pushdown (int i,int l,int r){
		int mid = (l + r) >> 1,lson = i << 1,rson = i << 1 | 1;
		if (tagv[i]) AddTag (lson,l,mid,tagv[i]),AddTag (rson,mid + 1,r,tagv[i]),tagv[i] = 0;
		if (maxv[lson] > maxv[i] && seca[lson] < maxv[i]) MinTag (lson,l,mid,maxv[i]);
		if (maxv[rson] > maxv[i] && seca[rson] < maxv[i]) MinTag (rson,mid + 1,r,maxv[i]);
		if (minv[lson] < minv[i] && seci[lson] > minv[i]) MaxTag (lson,l,mid,minv[i]);
		if (minv[rson] < minv[i] && seci[rson] > minv[i]) MaxTag (rson,mid + 1,r,minv[i]);
	}
	void build (int i,int l,int r){
		if (l == r){
			int x = 0;
			sumv[i] = maxv[i] = minv[i] = x,cnta[i] = cnti[i] = 1,seca[i] = -INF,seci[i] = INF;
			return ;
		}
		int mid = (l + r) >> 1;
		build (i << 1,l,mid);
		build (i << 1 | 1,mid + 1,r);
		Pushup (i);
	}
	void ChangeMax (int i,int l,int r,int tl,int tr,int v){
		if (minv[i] >= v) return ;
		if (l >= tl && r <= tr && v < seci[i]) return MaxTag (i,l,r,v);
		int mid = (l + r) >> 1;Pushdown (i,l,r);
		if (tl <= mid) ChangeMax (i << 1,l,mid,tl,tr,v);
		if (tr > mid) ChangeMax (i << 1 | 1,mid + 1,r,tl,tr,v);
		Pushup (i);
	}
	void ChangeSum (int i,int l,int r,int tl,int tr,int v){
		if (tl > tr) return ;
		if (l >= tl && r <= tr) return AddTag (i,l,r,v);
		int mid = (l + r) >> 1;Pushdown (i,l,r);
		if (tl <= mid) ChangeSum (i << 1,l,mid,tl,tr,v);
		if (tr > mid) ChangeSum (i << 1 | 1,mid + 1,r,tl,tr,v);
		Pushup (i);
	} 
	int QueryMax (int i,int l,int r,int tl,int tr){
		if (l >= tl && r <= tr) return maxv[i];
		int mid = (l + r) >> 1;Pushdown (i,l,r);int ans = -INF;
		if (tl <= mid) ans = max (ans,QueryMax (i << 1,l,mid,tl,tr));
		if (tr > mid) ans = max (ans,QueryMax (i << 1 | 1,mid + 1,r,tl,tr));
		return ans;
	}
}Tree; 

signed main(){
	read (n);
	for (Int i = 1;i <= n;++ i) read (a[i]);
	Tree.build (1,1,n);
	for (Int i = 1;i <= n;++ i)
		Tree.ChangeSum (1,1,n,a[i],n,1),
		Tree.ChangeSum (1,1,n,1,a[i] - 1,-1),
		Tree.ChangeMax (1,1,n,1,n,0),sz[i][0] = Tree.QueryMax (1,1,n,a[i],a[i]);
	Tree.build (1,1,n);
	for (Int i = 1;i <= n;++ i)
		Tree.ChangeSum (1,1,n,1,a[i],1),
		Tree.ChangeSum (1,1,n,a[i] + 1,n,-1),
		Tree.ChangeMax (1,1,n,1,n,0),sz[i][1] = Tree.QueryMax (1,1,n,a[i],a[i]);
	Tree.build (1,1,n);
	for (Int i = n;i >= 1;-- i)
		Tree.ChangeSum (1,1,n,a[i],n,1),
		Tree.ChangeSum (1,1,n,1,a[i] - 1,-1),
		Tree.ChangeMax (1,1,n,1,n,0),sf[i][0] = Tree.QueryMax (1,1,n,a[i],a[i]);
	Tree.build (1,1,n);
	for (Int i = n;i >= 1;-- i)
		Tree.ChangeSum (1,1,n,1,a[i],1),
		Tree.ChangeSum (1,1,n,a[i] + 1,n,-1),
		Tree.ChangeMax (1,1,n,1,n,0),sf[i][1] = Tree.QueryMax (1,1,n,a[i],a[i]);
    for (Int i = 1;i <= n;++ i){
		int h1 = (sz[i][0] + sf[i][0] - 1 - 1) / 2,h2 = (sz[i][1] + sf[i][1] - 1) / 2;
		write (max (max (h1,h2),0)),putchar (' ');
	}
	putchar ('\n');
	return 0;
}
/*
第i棵线段树维护数字x后缀<=x的个数->x的最大值
显然在加入a[i]之后>=a[i]的数字都会+1，<a[i]的都会减一
然后每时每刻都需要与0取较大值

似乎是一个吉司机线段树 

然后
*/
```