#include<bits/stdc++.h>
#define int long long
using namespace std;
#define fi first
#define sc second
#define pii pair<int,int>
#define pdd pair<double,double>
#define pb push_back
#define umap unordered_map
#define mset multiset
#define pq priority_queue
#define ull unsigned long long
#define i128 __int128
#define ld long double
#define fixs fixed<<setprecision
#define FileIn(x) freopen(x".in","r",stdin)
#define FileOut(x) freopen(x".out","w",stdout)
#define FileIO(x) FileIn(x),FileOut(x);
int n,q,res;
set<pii> s;
void solve(){
    cin>>n>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        if(s.empty()) s.insert({l,r}),res=max(res,r-l+1);
        else{
            auto it=s.upper_bound({l,l});
            int L=l,R=r;
            vector<pii> del;
            // cout<<l<<" "<<r<<endl;
            if((*it).fi>=l&&(*it).fi<=r+1) R=(*it).sc,del.pb(*it); 
            it--;
            if((*it).sc>=l-1&&(*it).sc<=r) L=(*it).fi,del.pb(*it);
            for(pii p:del) s.erase(p);
            res=max(res,R-L+1),s.insert({L,R});
        }
        // for(pii p:s) cout<<p.fi<<" "<<p.sc<<endl;
        cout<<res<<endl;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}
/*
Samples
input:

output:

THINGS TODO:
检查freopen，尤其是后缀名
检查空间
检查调试语句是否全部注释
*/