#include <bits/stdc++.h>
using namespace std;
const int MX = 1e6 + 5, INF = 1e9;
int n, p[MX], val[MX], tpos[MX], a[MX], T, N;
struct Convert {
int seg[MX<<2];
void build(int l, int r, int id){
seg[id] = r - l;
if(r - l == 1) return;
int m = (l+r)>>1;
build(l, m, id<<1);
build(m, r, id<<1|1);
}
void upd(int p, int l, int r, int id){
seg[id]--;
if(r - l == 1) return;
int m = (l+r)>>1;
p < m ? upd(p, l, m, id<<1) : upd(p, m, r, id<<1|1);
}
int kth(int k, int l, int r, int id){
if(r - l == 1) return l;
int m = (l+r)>>1;
if(seg[id<<1] >= k) return kth(k, l, m, id<<1);
return kth(k - seg[id<<1], m, r, id<<1|1);
}
void run(){
build(1, n+1, 1);
for(int i = n; i >= 1; i--){
p[i] = kth(p[i], 1, n+1, 1);
upd(p[i], 1, n+1, 1);
}
}
} conv;
struct Seg {
vector<int> st;
Seg(){}
Seg(int n){ st.assign(4*n+5, INF); }
void upd(int p, int v, int l, int r, int id){
if(r - l == 1){
st[id] = min(st[id], v);
return;
}
int m = (l+r)>>1;
p < m ? upd(p, v, l, m, id<<1) : upd(p, v, m, r, id<<1|1);
st[id] = min(st[id<<1], st[id<<1|1]);
}
int get(int s, int e, int l, int r, int id){
if(s >= r || l >= e) return INF;
if(s <= l && r <= e) return st[id];
int m = (l+r)>>1;
return min(get(s, e, l, m, id<<1), get(s, e, m, r, id<<1|1));
}
} seg[1505];
int res[MX];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
vector<int> comp;
for(int i=1;i<=n;i++){
cin >> p[i] >> val[i];
comp.push_back(val[i]);
}
conv.run();
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
N = comp.size();
for(int i=1;i<=n;i++){
a[p[i]] = lower_bound(comp.begin(), comp.end(), val[i]) - comp.begin() + 1;
tpos[p[i]] = i;
}
for(int i=1;i<=N;i++) seg[i] = Seg(N);
for(int i=1;i<=n;i++){
seg[1].upd(a[i], tpos[i], 1, N+1, 1);
for(int j=2;j<=a[i];j++){
int v = seg[j-1].get(1, a[i], 1, N+1, 1);
seg[j].upd(a[i], max(v, tpos[i]), 1, N+1, 1);
}
}
for(int k=1;k<=N;k++){
int tm = seg[k].st[1];
if(tm < INF) res[tm] = k;
}
for(int i=1;i<=n;i++){
res[i] = max(res[i], res[i-1]);
cout << res[i] << "\n";
}
return 0;
}
