#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
using ll=long long;
void startupcpp(){
  cin.tie(0);
  ios::sync_with_stdio(false);
}

// Merge:0->interval set,1->point set
template<typename T,int Merge=1>
struct rangeset:set<pair<T,T>>{
private:
  using P=pair<T,T>;
  using seitr=_Rb_tree_const_iterator<P>;
  const T TINF=numeric_limits<T>::max()/2;
public:
  // There are all [L,R] (not [L,R) )
  rangeset(){
    this->emplace(-TINF,-TINF);
    this->emplace(TINF,TINF);
  }

  // [L,R] covered?
  bool covered(T L,T R){
    // assert(L<=R);
    seitr itr(--this->lower_bound(P(L+1,L)));
    return R<=itr->second;
  }
  bool covered(T x){
    return covered(x,x);
  }

  // what is covered [L,R] (not cover->return [-TINF,-TINF])
  P covered_by(T L,T R){
    // assert(L<=R);
    seitr itr(--this->lower_bound(P(L+1,L)));
    if(R<=itr->second)return *itr;
    else return *(this->begin());
  }
  P covered_by(T x){
    return covered_by(x,x);
  }
  //insert [L,R] and merge, return (how many add point or interval)
  pair<seitr,T> insert(T L,T R){
    // assert(L<=R);
    seitr itr(--this->lower_bound(P(L+1,L)));
    if(R<=itr->second)return pair<seitr,T>(itr,0);

    T deletecnt(0);
    if(itr->second<L-Merge){
      ++itr;
    }else{
      L=itr->first;
      deletecnt=itr->second-itr->first+Merge;
      itr=this->erase(itr);
    }
    while(itr->second<=R){
      deletecnt+=itr->second-itr->first+Merge;
      itr=this->erase(itr);
    }
    if(itr->first<=R+Merge){
      R=itr->second;
      deletecnt+=itr->second-itr->first+Merge;
      itr=this->erase(itr);
    }
    itr=this->emplace_hint(itr,L,R);
    return pair<seitr,T>(itr,R-L+Merge-deletecnt);
  }
  pair<seitr,T> insert(T x){
    // assert(Merge==1);
    return insert(x,x);
  }
  //delete intersect [L,R], return (how many erase point or interval)
  T remove(T L,T R){
    // assert(L<=R);
    seitr itr(--this->lower_bound(P(L+1,L)));
    if(R<=itr->second){
      if(itr->first!=L)this->emplace_hint(itr,itr->first,L-Merge);
      if(itr->second!=R)this->emplace_hint(next(itr),R+Merge,itr->second);
      this->erase(itr);
      return R-L+Merge;
    }
    T deletecnt(0);
    if(itr->second<=L-Merge){
      ++itr;
    }else{
      deletecnt=itr->second-L+Merge;
      this->emplace_hint(itr,itr->first,L-Merge);
      itr=this->erase(itr);
    }
    while(itr->second<=R){
      deletecnt+=itr->second-itr->first+Merge;
      itr=this->erase(itr);
    }
    if(itr->first<R+Merge){
      deletecnt+=R-itr->first+Merge;
      this->emplace_hint(next(itr),R+Merge,itr->second);
      this->erase(itr);
    }
    return deletecnt;
  }
  T remove(T x){
    // assert(Merge==1);
    return remove(x,x);
  }
  T mex(T x){
    // assert(Merge==1);
    seitr itr(this->lower_bound(P(x,x)));
    if(itr->first<=x)return itr->second+1;
    else return x+1;
  }
};
ll ans;
int main(){
  scanf("%lld");
  int N;
  scanf("%d",&N);
  rangeset<ll> se;
  for(int i=0;i<N;++i){
    ll L,R;
    scanf("%lld %lld",&L,&R);
    auto itr=*se.insert(L,R).first;
    ans=max(ans,itr.second-itr.first+1);
    printf("%lld\n",ans);
  }
}