#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin() , x.end()
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pb push_back
#define qb pop_back
#define F first
#define S second
#define wall cerr<<"--------------------------------------"<<endl
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#pragma GCC optimize("Ofast")
typedef long long ll;
typedef double db;
const ll INF = 1e9;
const ll maxn = 2e6 + 10;
const ll SQRT = 2e3 + 10;
int n , Ps[maxn] , Vl[maxn] , a[maxn] , T[maxn];
int Lz[maxn<<2] , Ar[maxn<<2];
void Build(int tl=1 , int tr=n , int v=1)
{
if(tl==tr){
Ar[v] = tl;
return;
}
int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
Build(tl,mid,ml); Build(mid+1,tr,mr);
Ar[v] = max(Ar[ml],Ar[mr]);
}
inline void Shift(int tl , int tr , int v)
{
int ml=(v<<1) , mr=(v<<1)|1;
Ar[v] += Lz[v];
Ar[v] = max(0,Ar[v]);
if(tl!=tr){
Lz[ml] += Lz[v];
Lz[mr] += Lz[v];
}
Lz[v] = 0;
}
void Upd(int l , int r , int tl=1 , int tr=n , int v=1)
{
Shift(tl,tr,v);
if(l>r)return;
if(l==tl && r==tr){
Lz[v] --;
Shift(tl,tr,v);
return;
}
int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
Upd(l,min(r,mid),tl,mid,ml);
Upd(max(l,mid+1),r,mid+1,tr,mr);
Ar[v] = max(Ar[ml],Ar[mr]);
}
void Change(int pos , int tl=1 , int tr=n , int v=1)
{
Shift(tl,tr,v);
if(tl==tr){
Ar[v] = 0;
return;
}
int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
if(pos<=mid)Change(pos,tl,mid,ml);
else Change(pos,mid+1,tr,mr);
Ar[v] = max(Ar[ml],Ar[mr]);
}
int Find(int val , int tl=1 , int tr=n , int v=1)
{
Shift(tl,tr,v);
if(tl==tr){
return tl;
}
int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
Shift(tl,mid,ml); Shift(mid+1,tr,mr);
if(Ar[ml]>=val){
return Find(val,tl,mid,ml);
}else{
return Find(val,mid+1,tr,mr);
}
}
// just to find the array
/******/
struct segment
{
int seg[SQRT<<2];
void build(int tl=1 , int tr=SQRT , int v=1)
{
seg[v] = INF;
if(tl==tr){
return;
}
int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
build(tl,mid,ml); build(mid+1,tr,mr);
}
void upd(int pos , int val , int tl=1 , int tr=SQRT , int v=1)
{
if(tl==tr){
seg[v] = min(val,seg[v]);
return;
}
int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
if(pos<=mid)upd(pos , val , tl , mid , ml);
else upd(pos , val , mid+1 , tr , mr);
seg[v] = min(seg[ml] , seg[mr]);
}
int ask(int l , int r , int tl=1 , int tr=SQRT , int v=1)
{
if(l>r)return INF;
if(l==tl && r==tr){
return seg[v];
}
int mid=(tl+tr)>>1 , ml=(v<<1) , mr=(v<<1)|1;
return min(ask(l,min(r,mid),tl,mid,ml) ,
ask(max(l,mid+1),r,mid+1,tr,mr));
}
int node()
{
return seg[1];
}
}seg[SQRT+1];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
cin>>n;
for(int i=1; i<=n; i++){
cin>>Ps[i]>>Vl[i];
}
Build();
for(int i=n; i>=1; i--){
int pos = Find(Ps[i]);
Change(pos);
Upd(pos+1,n);
a[pos] = Vl[i];
T[pos] = i;
}
// we found the array
/***/
vector<pll> ve;
for(int i=1; i<=n; i++){
ve.push_back({a[i],i});
}
sort(all(ve));
int res = 1;
a[ve[0].S] = 1;
for(int i=1; i<n; i++){
if(ve[i].F != ve[i-1].F){
res++;
}
a[ve[i].S] = res;
}
// comperes
/**/
for(int i=1; i<=SQRT; i++){
seg[i].build();
}
for(int i=1; i<=n; i++){
seg[1].upd(a[i],T[i]);
for(int j=2; j<=a[i]; j++){
int x = seg[j-1].ask(1,a[i]-1);
x = max(x , T[i]);
seg[j].upd(a[i],x);
}
}
for(int i=1; i<=n; i++)a[i]=0;
for(int i=1; i<=SQRT; i++){
int x = seg[i].node();
//cout<<x<<"\n";
if(x==INF)continue;
a[x] = i;
}
for(int i=1; i<=n; i++){
a[i] = max(a[i-1],a[i]);
}
for(int i=1; i<=n; i++)cout<<a[i]<<"\n";
return 0;
}
/*
6
1 7
2 10
2 11
2 8
4 10
1 2
*/
/*
ans =
1
2
2
3
3
4
*/
/*
by
_____ _____ _____ _____
/\ \ /\ \ /\ \ /\ \
/::\ \ /::\ \ /::\____\ /::\ \
/::::\ \ /::::\ \ /:::/ / \:::\ \
/::::::\ \ /::::::\ \ /:::/ / \:::\ \
/:::/\:::\ \ /:::/\:::\ \ /:::/ / \:::\ \
/:::/__\:::\ \ /:::/__\:::\ \ /:::/____/ \:::\ \
/::::\ \:::\ \ \:::\ \:::\ \ /::::\ \ /::::\ \
/::::::\ \:::\ \ ___\:::\ \:::\ \ /::::::\ \ _____ ____ /::::::\ \
/:::/\:::\ \:::\ \ /\ \:::\ \:::\ \ /:::/\:::\ \ /\ \ /\ \ /:::/\:::\ \
/:::/ \:::\ \:::\____\/::\ \:::\ \:::\____\/:::/ \:::\ /::\____\/::\ \/:::/ \:::\____\
\::/ \:::\ /:::/ /\:::\ \:::\ \::/ /\::/ \:::\ /:::/ /\:::\ /:::/ \::/ /
\/____/ \:::\/:::/ / \:::\ \:::\ \/____/ \/____/ \:::\/:::/ / \:::\/:::/ / \/____/
\::::::/ / \:::\ \:::\ \ \::::::/ / \::::::/ /
\::::/ / \:::\ \:::\____\ \::::/ / \::::/____/
/:::/ / \:::\ /:::/ / /:::/ / \:::\ \
/:::/ / \:::\/:::/ / /:::/ / \:::\ \
/:::/ / \::::::/ / /:::/ / \:::\ \
/:::/ / \::::/ / /:::/ / \:::\____\
\::/ / \::/ / \::/ / \::/ /
\/____/ \/____/ \/____/ \/____/
*/
//NOGHRE SHODANAM BAD NIST :_)
