#include template class IntervalSet : std::set> { private: const T INF = std::numeric_limits::max() - 65; bool isMergeAdjacent; public: /** * @brief Construct a new Interval Set object * * @param f if merge adjacent interval */ IntervalSet(bool f) : isMergeAdjacent(f) { this->emplace(-INF - 1, -INF); this->emplace(INF, INF + 1); } auto get(T p) const { auto it = this->upper_bound({p, INF}); if(it == this->begin() || (--it)->second < p) return this->end(); return it; } void insert(T l, T r) { auto it = std::prev(this->lower_bound({l, r})); if(it->first <= l && l + !isMergeAdjacent <= it->second) { l = std::min(l, it->first); r = std::max(r, it->first); this->erase(it); } it = this->lower_bound({l, r}); while(1) { if(l <= it->first && it->first <= r) { r = std::max(r, it->second); it = this->erase(it); } else break; } this->emplace(l, r); } void remove(T l, T r) {} bool same(T p, T q) const { auto it = get(p); return it != this->end() && it->first <= q && q <= it->second; } }; int main() { long long d, q; std::cin >> d >> q; IntervalSet st(true); long long res = 0; for(int i = 0; i < q; i++) { long long x, y; std::cin >> x >> y; y++; st.insert(x, y); auto it = st.get(x); res = std::max(it->second - it->first, res); std::cout << res << std::endl; } }