#include <bits/stdc++.h>
using namespace std;
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
const int MXN = 1e6+5, inf = 1e9;
int n;
namespace converter {
int seg[MXN<<2];
void build(int l=1, int r=n+1, int id=1) {
seg[id] = r-l;
if(r-l == 1) return;
build(l, mid, lc);
build(mid, r, rc);
}
void upd(int p, int l=1, int r=n+1, int id=1) {
seg[id]--;
if(r-l==1) return;
p<mid ? upd(p, l, mid, lc) : upd(p, mid, r, rc);
}
int kth(int k, int l=1, int r=n+1, int id=1) {
if(r-l==1) return l;
return seg[lc]>=k ? kth(k, l, mid, lc) : kth(k-seg[lc], mid, r, rc);
}
inline void convert(int p[MXN]) {
build();
for(int i=n; i>=1; i--) upd(p[i] = kth(p[i]));
}
}
int p[MXN], a[MXN], b[MXN], t[MXN], ans[MXN], N;
vector<int> cmp;
inline int GI(int x) { return lower_bound(cmp.begin(), cmp.end(), x)-cmp.begin()+1; }
struct Seg {
vector<int> seg;
void upd(int p, int x, int l=1, int r=N+1, int id=1) {
if(r-l == 1) {
seg[id] = min(seg[id], x);
return;
}
p<mid ? upd(p, x, l, mid, lc) : upd(p, x, mid, r, rc);
seg[id] = min(seg[lc], seg[rc]);
}
int get(int s, int e, int l=1, int r=N+1, int id=1) {
if(s>=r || l>=e) return inf;
if(s<=l && r<=e) return seg[id];
return min(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}
} seg[MXN];
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for(int i=1; i<=n; i++) cin >> p[i] >> b[i], cmp.push_back(b[i]);
converter::convert(p);
sort(cmp.begin(), cmp.end());
cmp.resize(unique(cmp.begin(), cmp.end())-cmp.begin());
for(int i=1; i<=n; i++) {
a[p[i]] = GI(b[i]);
t[p[i]] = i;
}
N = cmp.size();
for(int i=1; i<=N; i++) seg[i].seg = vector<int>(4*N+5, inf);
for(int i=1; i<=n; i++) {
seg[1].upd(a[i], t[i]);
for(int j=2; j<=a[i]; j++)
seg[j].upd(a[i], max(t[i], seg[j-1].get(1, a[i])));
}
for(int i=1; i<=N; i++)
if(seg[i].seg[1]!=inf)
ans[seg[i].seg[1]] = i;
for(int i=1; i<=n; i++) {
ans[i] = max(ans[i-1], ans[i]);
cout << ans[i] << '\n';
}
return 0;
}
