#include <vector>
#include <iostream>

using namespace std;
using ll = long long;
#include <set>
#include <limits>
template<typename T>

struct RangeManage {
  set<pair<T, T>> ranges;
  pair<T, T> add(T l, T r) {
    T nl = l;T nr = r;
    while (true) {
      auto itr = ranges.lower_bound({l, -numeric_limits<T>::max()});
      if (itr == ranges.end()) break;
      if ((*itr).first > r+1) break;
      nr = max(nr, (*itr).second);
      ranges.erase(itr);
    }
    auto itr = ranges.lower_bound({l, numeric_limits<T>::max()});
    if (itr != ranges.begin()) {
      itr--;
      if ((*itr).second >= l-1) {
        nl = min(nl, (*itr).first);
        nr = max(nr, (*itr).second);
        ranges.erase(itr);
      }
    }
    ranges.insert({nl, nr});
    return {nl, nr};
  }

};
int main() {
  ll D;int Q;cin >> D >> Q;
  RangeManage<ll> Range;
  ll ret = 0;
  while (Q--) {
    ll a, b;cin >> a >> b;
    auto res = Range.add(a, b);
    ret = max(ret, res.second-res.first+1);
    cout << ret << endl;
  }
}