#include using namespace std; template class IntervalSet{ /* insert(l, r): 区間[l, r)を挿入 区間が被っているものはマージ O(logN) erase(l, r): 区間[l, r)と被っている区間をすべて削除 O(logN) */ public: set> st; IntervalSet(T INF){ st.insert({-INF, -INF}); st.insert({INF, INF}); }; array insert(T l, T r){ // 区間[l, r)を挿入 区間が被っているものはマージ O(logN) // return マージした区間[l, r) auto it = st.lower_bound({l, r}); auto itl = it, itr = it; itl--; while (itl != st.begin() and l <= (*itl)[1]){ r = max(r, (*itl)[1]); l = min(l, (*itl)[0]); itl--; } while (itr != st.end() and (*itr)[0] <= r){ r = max(r, (*itr)[1]); itr++; } st.erase(++itl, itr); st.insert({l, r}); return {l, r}; } void erase(T l, T r){ // erase(l, r): 区間[l, r)と被っている区間をすべて削除 O(logN) auto res = insert(l, r); st.erase(res); } }; int main(){ int64_t d, q; cin >> d >> q; int64_t ma = 0; IntervalSet st(2e18); for (int i = 0; i < q; i++){ int64_t l, r; cin >> l >> r; r++; auto res = st.insert(l, r); ma = max(ma, res[1] - res[0]); cout << ma << endl; } }