#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

struct RNG {
  ll l, r;
  bool operator<(const RNG& a) const {
    return r < a.r;
  }
};

class MaxRange {
  ll max_range;
  set<RNG> rngs;
public:
  MaxRange():max_range(0){}

  void add(const RNG& rng){
    ll nl = rng.l, nr = rng.r;
    
    auto bgn = rngs.lower_bound((RNG){nl-1,nl-1});
    auto it = bgn;
    for(; it != rngs.end(); it++){
      if(it->l < rng.r){
        nl = min(nl, it->l);
        nr = max(nr, it->r);
      }else{
        break;
      }
    }
    
    rngs.erase(bgn, it);
    rngs.insert((RNG){nl,nr});
    max_range = max(max_range, nr+1-nl);
  }

  ll get_max(){
    return max_range;
  }
};



int main(){
  ll D;
  int Q;
  cin >> D >> Q;

  MaxRange mr;
  
  rep(i,Q){
    ll A, B;
    cin >> A >> B;
    mr.add((RNG){A,B});
    cout << mr.get_max() << endl;
  }
  
  return 0;
}