#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
const int inf=1e6+8;
int n,m;
int l[N],r[N];
int stk[N],top;
struct segtree{
	int tr[N*4],lz[N*4],p[N*4];
	void Pushup(int x)
	{
		if(tr[x*2]<=tr[x*2+1]) tr[x]=tr[x*2],p[x]=p[x*2];
		else tr[x]=tr[x*2+1],p[x]=p[x*2+1];
	} 
	void Pushdown(int x)
	{
		if(!lz[x]) return;
		tr[x*2]+=lz[x];
		tr[x*2+1]+=lz[x];
		lz[x*2]+=lz[x];
		lz[x*2+1]+=lz[x];
		lz[x]=0;
	}
	void modify(int l,int r,int L,int R,int x,int v)
	{
		if(l>R||r<L) return;
		if(l>=L&&r<=R)
		{
			tr[x]+=v;
			lz[x]+=v;
			if(l==r) p[x]=l;
			return;
		}
		int mid=(l+r)/2;
		Pushdown(x);
		modify(l,mid,L,R,x*2,v);
		modify(mid+1,r,L,R,x*2+1,v);
		Pushup(x);
	}
	int query(int l,int r,int p,int x)
	{
		if(l==r) return tr[x];
		int mid=(l+r)/2;
		Pushdown(x);
		if(p<=mid) return query(l,mid,p,x*2);
		else return query(mid+1,r,p,x*2+1);
	}
}tr1,tr2,tr3;
int ans[N];
struct node{
	int p,id;
};
vector<node> E[N];
int main()
{
	freopen("m.txt","w",stdout);
	scanf("%d",&n);
//	scanf("%d%d",&n,&m);
	srand(17);
	for(int i=1;i<=n;i++) 
	{
		l[i]=rand()%10,r[i]=rand()%10;
		if(l[i]>r[i]) swap(l[i],r[i]);
	}
//	for(int i=1;i<=n;i++)
//		scanf("%d%d",&l[i],&r[i]);
	tr1.modify(1,n,1,n,1,inf);
	tr2.modify(1,n,1,n,1,inf);
//	for(int i=1;i<=m;i++)
//	{
//		int l,r;
//		scanf("%d%d",&l,&r);
//		E[l].push_back((node){r,i});
//	}
	for(int i=n;i>=1;i--)
	{
		tr1.modify(1,n,i,i,1,l[i]-inf);
		tr2.modify(1,n,i,i,1,r[i]+1-inf);
		while(1)
		{
			int l1=tr1.p[1],l2=tr2.p[1];
			if(tr1.tr[1]>0&&tr2.tr[1]>0) break;
			if(tr1.tr[1]>0) l1=inf;
			if(tr2.tr[1]>0) l2=inf;
			if(l1<l2)
			{
				tr1.modify(1,n,l1,l1,1,inf);
				tr1.modify(1,n,l1+1,n,1,-1);
				tr2.modify(1,n,l1+1,n,1,-1);
				tr3.modify(1,n,l1,n,1,1);
			}
			else
			{
				tr2.modify(1,n,l2,l2,1,inf);
				tr1.modify(1,n,l2+1,n,1,1);
				tr2.modify(1,n,l2+1,n,1,1);
				tr3.modify(1,n,l2,n,1,-1);
			}
		}
		for(int j=i;j<=n;j++) printf("%d ",tr3.query(1,n,j,1));
		printf("\n");
		for(auto u:E[i]) ans[u.id]=tr3.query(1,n,u.p,1);
	}
//	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}