#include #include #include #include #include template struct RangeSet { private: const T TINF = std::numeric_limits::max() / 2; std::set> st; public: RangeSet() { st.emplace(-TINF, -TINF + 1); st.emplace(TINF, TINF + 1); } //[l, r) is covered? bool covered(const T l, const T r) { assert(l < r); auto itr = prev(st.lower_bound({l + 1, -TINF})); return itr->first <= l and r <= itr->second; } //[x, x + 1) is covered? bool covered(const T x) { return covered(x, x + 1); } //return section which covers[l, r) //if not exists, return[-TINF, -TINF) std::pair covered_by(const T l, const T r) { assert(l < r); auto itr = prev(st.lower_bound({l + 1, -TINF})); if(itr->first <= l and r <= itr->second) return *itr; return {-TINF, -TINF}; } //return section which covers[x, x + 1) //if not exists, return[-TINF, -TINF) std::pair covered_by(const T x) { return covered_by(x, x + 1); } //insert[l, r), and return increment T insert(T l, T r) { if(l >= r) return 0; auto itr = prev(st.lower_bound({l + 1, -TINF})); if(itr->first <= l and r <= itr->second) return T(0); T sum_erased = T(0); if(itr->first <= l and l <= itr->second) { l = itr->first; sum_erased += itr->second - itr->first; itr = st.erase(itr); } else itr = next(itr); while(r > itr->second) { sum_erased += itr->second - itr->first; itr = st.erase(itr); } if(itr->first <= r) { sum_erased += itr->second - itr->first; r = itr->second; st.erase(itr); } st.emplace(l, r); return r - l - sum_erased; } //insert[x, x + 1), and return increment T insert(const T x) { return insert(x, x + 1); } // erase [l, r), and return decrement T erase(const T l, const T r) { assert(l < r); auto itr = prev(st.lower_bound({l + 1, -TINF})); if(itr->first <= l and r <= itr->second) { if(itr->first < l) st.emplace(itr->first, l); if(r < itr->second) st.emplace(r, itr->second); st.erase(itr); return r - l; } T ret = T(0); if(itr->first <= l and l < itr->second) { ret += itr->second - l; if(itr->first < l) st.emplace(itr->first, l); itr = st.erase(itr); } else itr = next(itr); while(itr->second <= r) { ret += itr->second - itr->first; itr = st.erase(itr); } if(itr->first < r) { ret += r - itr->first; st.emplace(r, itr->second); st.erase(itr); } return ret; } // erase [x, x + 1), and return decrement T erase(const T x) { return erase(x, x + 1); } int size() { return (int)st.size() - 2; } int mex(const T x = 0) { auto itr = prev(st.lower_bound({x + 1, -TINF})); if(itr->first <= x and x < itr->second) return itr->second; else return x; } T sum_all() const { T res = 0; for(auto &p : st) { if(std::abs(p.first) == TINF) continue; res += p.second - p.first; } return res; } std::set> get() const { std::set> res; for(auto &p : st) { if(std::abs(p.first) == TINF) continue; res.emplace(p.first, p.second); } return res; } void dump() const { std::cout << "Rangeset:"; for(auto &p : st) { if(std::abs(p.first) == TINF) continue; std::cout << "[" << p.first << "," << p.second << "),"; } std::cout << '\n'; } }; long long a, b, d, res; int q; int main() { scanf("%lld%d", &d, &q); RangeSet st; while(q--) { scanf("%lld%lld", &a, &b); st.insert(a, b + 1); auto [l, r] = st.covered_by(a); res = std::max(res, r - l); printf("%lld\n", res); } }