#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; }