#include using namespace std; using ll = long long; template using vt = vector; template using vvt = vector>; template using ttt = tuple; using tii = tuple; using vi = vector; #define rep(i,n) for(int i=0;i<(int)(n);i++) #define pb push_back #define mt make_tuple #define ALL(a) (a).begin(),(a).end() #define FST first #define SEC second #define DEB cerr<<"!"<0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;} inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;} /*Coding Space*/ //区間管理する奴 O(log 値域) template struct RangeMarge{ map m; // m[r] = l にすると実装楽 pair insert(T l, T r){ // [l,r]が返り値(実際の区間) auto l_it = m.lower_bound(l); auto r_it = m.lower_bound(r); if(l_it != m.end() && l_it->second <= l) l = l_it->second; if(r_it != m.end() && r_it->second <= r) r = r_it->first; m.erase(l_it, m.upper_bound(r)); m[r] = l; return make_pair(l,r); } pair get(T p){ //pが含まれる領域を返す auto p_it = m.upper_bound(p); return (p_it == m.end()?make_pair(T(),T()):*p_it); } }; int main(){ ll d,q; cin >> d >> q; ll ans = 0; RangeMarge rm; rep(i,q){ ll a,b; cin >> a >> b; auto p = rm.insert(a,++b); ans = max(ans, p.second - p.first); cout << ans << endl; } }