首先 $i$ 能嵌套到 $j$ 里当且仅当 $c_i < s_i \leq c_j < s_j$，这是一个偏序的关系。把嵌套关系视作链，在一条链上的都满足偏序关系，则我们要求的就是覆盖整个集合所需的最少链的条数。
根据 Dilworth 定理最小链覆盖等于最长反链，于是转化成求一个最大的集合，其中任意两个元素均不满足偏序关系，也就是 $c_i < c_j \land s_i > s_j$ 或 $c_i > c_j \land s_i < s_j$。考虑把这些点画到数轴上，元素 $i$ 就可以用线段 $[c_i, s_i)$ 表示，则两个元素不满足偏序关系当且仅当两条线段有交。于是这个集合中的线段两两有交，并且显然会交于同一点。
那我们维护每个点被线段覆盖的次数即可。具体地，插入一个线段就是对 $[c_i, s_i - 1]$ 区间 $+1$，并查询全局最大值。
直接离散化之后用线段树维护即可。
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define rep(i, a, b) for(int (i) = (a); (i) <= (b); (i) ++)
#define per(i, a, b) for(int (i) = (a); (i) >= (b); (i) --)
#define REP(i, l, r, k) for (int i = (l); i <= (r); i += k)
#define PER(i, l, r, k) for (int i = (l); i >= (r); i -= k)
#define ls x << 1
#define rs x << 1 | 1
#define umap unordered_map
#define uset unordered_set
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define x1 Sun
#define y1 Jude
void ckmin(int &x, int y) { x = std::min(x, y) ; }
void ckmax(int &x, int y) { x = std::max(x, y) ; }
int lowbit(int x) { return x & -x ; }
using namespace std;
const int maxn = 4e5 + 5 ;
// const int inf = ;
// const int mod = ;
int n, s[maxn], c[maxn] ;
struct sgt {
int l[maxn << 2], r[maxn << 2] ;
int mx[maxn << 2], tag[maxn << 2] ;
void Add(int x, int k) { mx[x] += k, tag[x] += k ; }
void pushup(int x) { mx[x] = max(mx[ls], mx[rs]) ; }
void pushdown(int x) {
if(!tag[x]) return ;
Add(ls, tag[x]) ; Add(rs, tag[x]) ;
tag[x] = 0 ;
}
void build(int x, int L, int R) {
l[x] = L, r[x] = R ;
if(L == R) return ;
int mid = (L + R) >> 1 ;
build(ls, L, mid) ;
build(rs, mid + 1, R) ;
}
void add(int x, int L, int R, int k) {
if(L <= l[x] && r[x] <= R) {
Add(x, k) ;
return ;
}
pushdown(x) ;
int mid = (l[x] + r[x]) >> 1 ;
if(L <= mid) add(ls, L, R, k) ;
if(R > mid) add(rs, L, R, k) ;
pushup(x) ;
}
} t ;
vector<int> node ;
void solve(){
cin >> n ;
rep(i, 1, n) {
cin >> s[i] >> c[i] ;
node.pb(s[i]) ; node.pb(c[i]) ;
}
sort(all(node)) ;
node.erase(unique(all(node)), node.end()) ;
int N = node.size() ;
t.build(1, 0, N - 1) ;
rep(i, 1, n) {
int ss = lower_bound(all(node), s[i]) - node.begin(), cc = lower_bound(all(node), c[i]) - node.begin() ;
if(cc <= ss - 1) t.add(1, cc, ss - 1, 1) ;
cout << t.mx[1] << endl ;
}
return ;
}
signed main(){
// freopen("box.in", "r", stdin) ;
// freopen("box.out", "w", stdout) ;
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T = 1 ;
// cin >> T ;
while(T -- ){
solve() ;
}
return 0 ;
}