#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<int(n); i++)
const i64 INF = 1001001001001001001;
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
using namespace std;


namespace nachia{

template<
    class S,
    S op(S l, S r)
>
struct Segtree {
private:
    int N;
    std::vector<S> A;
    int xN;

    void mergev(int i){
        if(i < N) A[i] = op(A[i*2], A[i*2+1]);
    }

    template<class E>
    int minLeft2(int r, E cmp, int a = 0, int b = 0, int i = -1) const {
        static S x;
        if(i == -1){ a=0; b=N; i=1; x=A[0]; }
        if(r <= a) return a;
        if(b <= r){
            S nx = op(A[i], x);
            if(cmp(nx)){ x = nx; return a; }
        }
        if(b - a == 1) return b;
        int q = minLeft2(r, cmp, (a+b)/2, b, i*2+1);
        if(q > (a+b)/2) return q;
        return minLeft2(r, cmp, a, (a+b)/2, i*2);
    }
    
    template<class E>
    int maxRight2(int l, E cmp, int a = 0, int b = 0, int i = -1) const {
        static S x;
        if(i == -1){ a=0; b=N; i=1; x=A[0]; }
        if(b <= l) return b;
        if(l <= a){
            S nx = op(x, A[i]);
            if(cmp(nx)){ x = nx; return b; }
        }
        if(b - a == 1) return a;
        int q = maxRight2(l, cmp, a, (a+b)/2, i*2);
        if(q < (a+b)/2) return q;
        return maxRight2(l, cmp, (a+b)/2, b, i*2+1);
    }

public:
    Segtree() : N(0) {}
    Segtree(int n, S e) : xN(n) {
        N = 1; while (N < n) N *= 2;
        A.assign(N * 2, e);
    }
    Segtree(const std::vector<S>& a, S e) : Segtree(a.size(), e){
        for(int i=0; i<(int)a.size(); i++) A[i + N] = a[i];
        for(int i=N-1; i>=1; i--) mergev(i);
    }

    S getE() const { return A[0]; }

    void set(int p, S x){
        p += N; A[p] = x;
        for(int d=1; (1<<d)<=N; d++) mergev(p>>d);
    }

    S get(int p) const { return A[N+p]; }

    S prod(int l, int r) const {
        l += N; r += N;
        S ql = A[0], qr = A[0];
        while(l<r){
            if(l&1) ql = op(ql, A[l++]);
            if(r&1) qr = op(A[--r], qr);
            l /= 2;
            r /= 2;
        }
        return op(ql, qr);
    }

    S allProd() const { return A[1]; }

    // bool cmp(S)
    template<class E>
    int minLeft(int r, E cmp) const {
        return minLeft2(r, cmp);
    }

    // bool cmp(S)
    template<class E>
    int maxRight(int l, E cmp) const {
        int x = maxRight2(l, cmp);
        return x > xN ? xN : x;
    }
};

} // namespace nachia
#include <functional>
#include <utility>

namespace nachia {
    template<class T, class Cmp = std::less<T>>
    struct PointSetRangeMin{
    private:
        static T minop(T l, T r){ return std::min(l, r, Cmp()); }
        using Base = Segtree<T, minop>;
        Base base;
        Cmp cmpx;
    public:
        PointSetRangeMin() {}
        PointSetRangeMin(int len, T INF)
            : base(len, INF){}
        PointSetRangeMin(const std::vector<T>& init, T INF)
            : base(init, INF){}
        T min(int l, int r){ return base.prod(l, r); }
        T min(){ return base.allProd(); }
        void set(int pos, T val){ base.set(pos, val); }
        T getinf() const { return base.getE(); }
        void setinf(int pos){ set(pos, getinf()); }
        T get(int pos){ return base.get(pos); }
        void chmin(int pos, T val){ base.set(pos, minop(get(pos), val)); }
        int lBoundLeft(int from, T val){ return base.minLeft(from, [this,val](const T& x){ return cmpx(val, x); }); }
        int uBoundLeft(int from, T val){ return base.minLeft(from, [this,val](const T& x){ return !cmpx(x, val); }); }
        int lBoundRight(int from, T val){ return base.maxRight(from, [this,val](const T& x){ return cmpx(val, x); }); }
        int uBoundRight(int from, T val){ return base.maxRight(from, [this,val](const T& x){ return !cmpx(x, val); }); }
        template<class E>
        int minLeft(int r, E cmp){ return base.minLeft(r, cmp); }
        template<class E>
        int maxRight(int l, E cmp){ return base.maxRight(l, cmp); }
        int argmin(int l, int r){
            auto v = this->min(l, r);
            if(!cmpx(v, getinf())) return -1;
            return lBoundRight(l, v);
        }
    };
} // namespace nachia


struct LinkCutTree {
    struct S { int x; };
    static S op(S l, S r) { return { l.x + r.x }; }
    static S e() { return { 0 }; }
    static void reverseprod(S& x) {}
    struct F {  };
    static S mapping(F f, S x) { return x; }
    static F composition(F f, F x) { return x; }
    static F id() { return {}; }


    struct Node {
        Node* l = 0, * r = 0, * p = 0;
        S a = e();
        S prod = e();
        F f = id();
        // lazy & 1 : reverse
        // lazy & 2 : deta
        int lazy = 0;
        
        void prepareDown() {
            if(lazy & 2){
                if(l) {
                    l->a = mapping(f, l->a);
                    l->prod = mapping(f, l->prod);
                    l->f = composition(f, l->f);
                    l->lazy |= 2;
                }
                if(r) {
                    r->a = mapping(f, r->a);
                    r->prod = mapping(f, r->prod);
                    r->f = composition(f, r->f);
                    r->lazy |= 2;
                }
                f = id();
            }
            if (lazy & 1) {
                std::swap(l, r);
                if (l) { l->lazy ^= 1; reverseprod(l->prod); }
                if (r) { r->lazy ^= 1; reverseprod(r->prod); }
            }
            lazy = 0;
        }
        void prepareUp() {
            auto res = a;
            if(l) res = op(l->prod, res);
            if(r) res = op(res, r->prod);
            prod = res;
        }
        Node** p_parentchild() {
            if(!p) return nullptr;
            if(p->l == this) return &p->l;
            else if(p->r == this) return &p->r;
            return nullptr;
        }
        void rotL() {
            Node* t = p;
            Node** parentchild_p = t->p_parentchild();
            if(parentchild_p){ *parentchild_p = this; }
            p = t->p;
            t->p = this;
            t->r = l;
            if(l) l->p = t;
            l = t;
        }
        void rotR() {
            Node* t = p;
            Node** parentchild_p = t->p_parentchild();
            if(parentchild_p){ *parentchild_p = this; }
            p = t->p;
            t->p = this;
            t->l = r;
            if(r) r->p = t;
            r = t;
        }
    };

    std::vector<Node> A;
    LinkCutTree(int n = 0) {
        A.resize(n);
    }
    LinkCutTree(const std::vector<S>& a) : LinkCutTree(a.size()) {
        for (int i = 0; i < (int)a.size(); i++) A[i].prod = A[i].a = a[i];
    }
    Node* at(int idx) {
        return &A[idx];
    }
    void splay(Node* c) {
        c->prepareDown();
        while(true) {
            Node* p = c->p;
            if(!p) break;
            Node* pp = p->p;
            if(pp) pp->prepareDown();
            p->prepareDown();
            c->prepareDown();
            if(p->l == c){
                if(!pp){ c->rotR(); }
                else if(pp->l == p){ p->rotR(); c->rotR(); }
                else if(pp->r == p){ c->rotR(); c->rotL(); }
                else{ c->rotR(); }
            }
            else if(p->r == c){
                if(!pp){ c->rotL(); }
                else if(pp->r == p){ p->rotL(); c->rotL(); }
                else if(pp->l == p){ c->rotL(); c->rotR(); }
                else{ c->rotL(); }
            }
            else break;
            if(pp) pp->prepareUp();
            p->prepareUp();
        }
        c->prepareUp();
    }
    void expose(Node* c) {
        auto p = c;
        while(p){ splay(p); p = p->p; }
        p = c;
        while(p->p){ p->p->r = p; p = p->p; }
        splay(c);
        c->r = nullptr;
        c->prod = (c->l ? op(c->l->prod, c->a) : c->a);
    }
    void evert(Node* c) {
        expose(c);
        c->lazy ^= 1;
        reverseprod(c->prod);
        c->prepareDown();
    }
    void link(Node* c, Node* r) {
        if(c == r) return;
        evert(c);
        evert(r);
        if(c->p) return;
        c->p = r;
    }
    void cut(Node* c) {
        expose(c);
        if(!c->l) return;
        c->l->p = nullptr;
        c->l = nullptr;
    }
    // [u,v)
    // post : evert(u) , splayLC(v)
    Node* between(Node* u, Node* v) {
        if(u == v) return nullptr;
        evert(u);
        expose(v);
        v->l->prepareDown();
        return v->l;
    }
    S prod(Node* s, Node* t) {
        auto resv = between(s, t);
        if(!resv) return t->a;
        S res = resv->prod;
        res = op(res, t->a);
        return res;
    }
    S get(Node* p) {
        expose(p);
        return p->a;
    }
    void set(Node* p, S x) {
        expose(p);
        p->a = x;
        p->prepareUp();
    }
};



vector<int> T(int F, vector<pair<int,int>> D){
    int N = D.size();
    vector<vector<int>> I(F+1);
    rep(i,D.size()) I[D[i].second].push_back(i);
    auto ds = nachia::PointSetRangeMin<int>(F+1, 1001001001);
    vector<int> ans(N, N);
    rep(i,F+1){
        for(auto a : I[i]){
            int f = ds.min(D[a].first, F+1);
            chmin(ans[a], f);
        }
        sort(I[i].begin(), I[i].end());
        for(auto a : I[i]){
            ds.chmin(D[a].first, a);
        }
        for(auto a : I[i]){
            int f = ds.min(D[a].first+1, F+1);
            chmin(ans[a], f);
        }
    }
    vector<int> Q(N);
    rep(i,N) Q[i] = i;
    stable_sort(Q.begin(), Q.end(), [&](int l, int r){ return D[l] < D[r]; });
    rep(i,N-1) if(D[Q[i]] == D[Q[i+1]]) ans[Q[i+1]] = Q[i+1];
    return ans;
}


void testcase(){
    int N; cin >> N;
    vector<pair<int,int>> A(N);
    for(auto& [u,v] : A){ cin >> u >> v; v++; }
    auto I = T(N*2+2, A);
    //rep(i,N){ cout << I[i] << " "; } cout << endl;

    int Z = N*2+6;

    vector<vector<int>> D(N+1);
    rep(i,N) if(i != I[i]) D[I[i]].push_back(i);

    vector<int> ans;

    LinkCutTree lct(N+Z);
    rep(i,N) lct.set(lct.at(i), {1});
    rep(i,Z-1) lct.link(lct.at(N+i), lct.at(N+i+1));

    auto cut = [&](int u){
        //cout << "cut " << u << endl;
        lct.cut(lct.at(u));
        lct.evert(lct.at(N+Z-1));
    };

    auto link = [&](int u, int v){
        //cout << "link " << u << " " << v << endl;
        lct.link(lct.at(u), lct.at(v));
        lct.evert(lct.at(N+Z-1));
    };

    rep(i,N){
        for(auto u : D[i]){
            auto [l,r] = A[u];
            cut(u);
            cut(N+l);
            link(N+l, N+l+1);
        }
        if(I[i] != i){ 
            auto [l,r] = A[i];
            cut(N+l);
            link(N+l, i);
            link(i, N+r);
        }
        lct.evert(lct.at(N+Z-1));
        lct.expose(lct.at(N));
        cout << lct.at(N)->prod.x << "\n";
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    testcase();
    return 0;
}