#include <stdio.h>
#define N 1000000
#define K 1000000
#define N_ (1 << 20) /* N_ = pow2(ceil(log2(N))) */
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int st[N_ * 2], n_;
void build(int n) {
int i;
n_ = 1;
while (n_ < n)
n_ <<= 1;
for (i = 0; i < n_; i++)
st[n_ + i] = i < n ? 1 : 0;
for (i = n_ - 1; i > 0; i--)
st[i] = st[i << 1 | 0] + st[i << 1 | 1];
}
void update(int i, int x) {
for (i += n_; i > 0; i >>= 1)
st[i] += x;
}
int query(int k) {
int i = 1;
while (i < n_)
if (k < st[i << 1 | 0])
i = i << 1 | 0;
else
k -= st[i << 1 | 0], i = i << 1 | 1;
return i - n_;
}
int zz[K + 1], ll[K + 1], rr[K + 1], ii[K + 1], u_, l_, r_;
int node(int i) {
static int _ = 1;
zz[_] = rand_();
ii[_] = i;
return _++;
}
void split(int u, int i) {
if (u == 0) {
u_ = l_ = r_ = 0;
return;
}
if (ii[u] < i) {
split(rr[u], i);
rr[u] = l_, l_ = u;
} else if (ii[u] > i) {
split(ll[u], i);
ll[u] = r_, r_ = u;
} else {
u_ = u, l_ = ll[u], r_ = rr[u];
ll[u] = rr[u] = 0;
}
}
int merge(int u, int v) {
if (u == 0)
return v;
if (v == 0)
return u;
if (zz[u] < zz[v]) {
rr[u] = merge(rr[u], v);
return u;
} else {
ll[v] = merge(u, ll[v]);
return v;
}
}
int first(int u) {
return ll[u] == 0 ? ii[u] : first(ll[u]);
}
int last(int u) {
return rr[u] == 0 ? ii[u] : last(rr[u]);
}
int remove_first(int u) {
if (ll[u] == 0)
return rr[u];
ll[u] = remove_first(ll[u]);
return u;
}
int aa[N], dp[N], uu[K + 1], k;
void add(int i) {
int j, l, r;
while (1) {
if (dp[i] == k) {
uu[k++] = node(i);
return;
}
split(uu[dp[i]], i);
if (l_ && aa[last(l_)] < aa[i])
uu[dp[i]++] = merge(l_, r_);
else
break;
}
l = l_, r = r_;
while (r && aa[i] < aa[j = first(r)]) {
r = remove_first(r);
dp[j]++, add(j);
}
uu[dp[i]] = merge(merge(l, node(i)), r);
}
int main() {
static int ii[N], aa_[N];
int n, h, i;
scanf("%d", &n);
for (h = 0; h < n; h++)
scanf("%d%d", &ii[h], &aa_[h]), ii[h]--;
build(n);
for (h = n - 1; h >= 0; h--) {
i = ii[h] = query(ii[h]);
aa[i] = aa_[h];
update(i, -1);
}
for (h = 0; h < n; h++) {
add(ii[h]);
printf("%d\n", k);
}
return 0;
}
