#include<bits/stdc++.h>
using namespace std;
struct node
{
	int l,r,_max;
}a[114514*3*4];
struct node1
{
	int l,r,_min=INT_MAX;
}a1[114514*3*4];
int ans[114514*3];
int n,b[114514*3],Van,Ass;
void bld(int l,int r,int root)
{
	a[root].l=l;
	a[root].r=r;
	if(l==r)
	{
		a[root]._max=b[l];
		return;
	}
	int mid=(l+r)/2;
	bld(l,mid,root*2);
	bld(mid+1,r,root*2+1);
	a[root]._max=max(a[root*2]._max,a[root*2+1]._max);
}
void bld_min(int l,int r,int root)
{
	a1[root].l=l;
	a1[root].r=r;
	if(l==r)
	{
		a1[root]._min=b[l];
		return;
	}
	int mid=(l+r)/2;
	bld_min(l,mid,root*2);
	bld_min(mid+1,r,root*2+1);
	a1[root]._min=min(a1[root*2]._min,a1[root*2+1]._min);
}
void max_(int x,int y,int root,int k)
{
	if(x<=a[root].l&&a[root].r<=y)
	{
		if(b[k]>a[root]._max)
			Ass=max(a[root]._max,Ass);
		return;
	}
	int mid=(a[root].l+a[root].r)/2;
	if(x<=mid)
		max_(x,y,root*2,k);
	if(y>mid)
		max_(x,y,root*2+1,k);
}
void min_(int x,int y,int root,int k)
{
	if(x<=a1[root].l&&a1[root].r<=y)
	{
		if(b[k]<a1[root]._min)
			Van=min(a1[root]._min,Van);
		return;
	}
	int mid=(a1[root].l+a1[root].r)/2;
	if(x<=mid)
		min_(x,y,root*2,k);
	if(y>mid)
		min_(x,y,root*2+1,k);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>b[i];
	bld(1,n,1);
	bld_min(1,n,1);
	ans[b[1]]=0;
	for(int i=2;i<=n;i++)
	{
		ans[0]=-114514;
		Van=INT_MAX;//大于它的最小值  
		Ass=-114;//小于它的最大值
		max_(1,i-1,1,i);
		min_(1,i-1,1,i);
		if(Van==INT_MAX)
			Van=0;
		if(Ass==-114)
			Ass=0;
		int k;
		if(ans[Ass]<ans[Van])
			k=Van;
		else
			k=Ass;
		ans[b[i]]=ans[k]+1;
//		cout<<Van<<" "<<Ass<<endl;
	}
	int sum=0;
	cout<<0<<endl;
	for(int i=2;i<=n;i++)
	{
		sum+=ans[b[i]];
		cout<<sum<<endl;
	}
	
}