#include using namespace std; #define DBG cerr << '!' << endl; #define REP(i,n) for(ll (i) = (0);(i) < (n);++i) #define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i) #define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i)) #define PB push_back #define MP make_pair #define FI first #define SE second #define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;} #define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;} #define ALL(v) v.begin(),v.end() #define Decimal fixed< P; template class SectionManagement : public std::map { private: // if merge [l, c] and [c+1, r], set flagToMergeAdjacentSegment to true bool AdjacentMarge; public: SectionManagement(bool flag):AdjacentMarge(flag){} void print(){ cout << "print SectionManagement" << endl; for(auto it = this->begin();it != this->end();it++){ cout << (it->first) << ' ' << (it->second) << endl; } cout << "end print" << endl; } //該当の区間を得る、なければend() typename std::map::const_iterator get(T p) const{ auto it = this->upper_bound(p); if (it == this->begin() || (--it)->second < p) return this->end(); return it; } //挿入、被る所はひとつにまとめる。 void insert(T l,T r){ if(this->size() == 0){ (*this)[l] = r; // cout << "!" << endl; return; } auto it = this->upper_bound(l); //cout << "upper " << (it->first) << ' ' << (it->second) << endl; if(it == this->begin() && r + AdjacentMarge< it->first){ (*this)[l] = r; // cout << "!!" << endl; return; } if(it != this->begin() && r + AdjacentMarge < it->first && l > std::prev(it)->second + AdjacentMarge){ (*this)[l] = r; // cout << "!!!" << endl; return; } auto itl = it; //cout << "prev " << (std::prev(it)->first) << ' ' << (std::prev(it)->second) << endl; //cout << std::prev(it)->second + AdjacentMarge << endl; if(it != this->begin() && std::prev(it)->second + AdjacentMarge >= l){ --itl; l = min(l,itl->first); } while(it != this->end() && it->second <= r){ it++; } if(it->first > r + AdjacentMarge)--it; if(it != this->end())r = max(r,it->second); //cout << "l " << (itl->first) << ' ' << (itl->second) << endl; //cout << "r " << (it->first) << ' ' << (it->second) << endl; if(it != this->end())it++; this->erase(itl,it); (*this)[l] = r; } //同じ区間にあるか bool same(T p, T q) const { const auto it = get(p); return it != this->end() && it->first <= q && q <= it->second; } }; int main() { SectionManagement mp(true); ll d,q;cin >> d >> q; ll ans = 0; REP(_,q){ ll a,b;cin >> a >> b; mp.insert(a,b); auto it = mp.get(a); ans = max(ans,it->second - it->first + 1); cout << ans << endl; //mp.print(); } return 0; }