class Bit: def __init__(self, n): """ :param n: number of elements """ self.n = n self.tree = [0]*(n+1) self.depth = n.bit_length() - 1 def sum(self, i): """ return summation of elements in [0,i) """ s = 0 i -= 1 while i >= 0: s += self.tree[i] i = (i & (i + 1) )- 1 return s def build(self, array): """ bulid BIT from array """ for i, a in enumerate(array): self.add(i, a) def add(self, i, x): """ add x to i-th element """ while i < self.n: self.tree[i] += x i |= i + 1 def get(self, i, j): """ return summation of elements in [i,j) """ if i == 0: return self.sum(j) return self.sum(j) - self.sum(i) def lower_bound(self, x, equal=False): """ return tuple = (return maximum i s.t. a0+a1+...+ai < x (if not existing, -1 ) , a0+a1+...+ai ) if one wants to include equal (i.e., a0+a1+...+ai <= x), please set equal = True (Cation) We must assume that A_i>=0 """ sum_ = 0 pos = -1 # 1-indexed の時は pos = 0 if not equal: for i in range(self.depth, -1, -1): k = pos + (1 << i) if k < self.n and sum_ + self.tree[k] < x: # 1-indexed の時は k <= self.n sum_ += self.tree[k] pos += 1 << i if equal: for i in range(self.depth, -1, -1): k = pos + (1 << i) if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n sum_ += self.tree[k] pos += 1 << i return pos, sum_ def __getitem__(self, i): """ [a0, a1, a2, ...] """ if i<0: i=self.n+i return self.get(i, i+1) def __iter__(self): """ [a0, a1, a2, ...] """ for i in range(self.n): yield self.get(i, i+1) def __str__(self): text1 = " ".join(["element: "] + list(map(str, self))) text2 = " ".join(["cumsum(1-indexed): "] + list(str(self.sum(i)) for i in range(1, self.n + 1))) return "\n".join((text1, text2)) class SortedList2: """ if we need compress """ def __init__(self, data, A=[]): """ self.size: number of elements in BitSet """ self.data = sorted(list(set(data))) self.n = len(self.data) self.p = Bit(self.n + 1) self.size = 0 self.code = {} self.decode = [] for i, b in enumerate(self.data): self.code[b] = i self.decode.append(b) for a in A: self.add(a) def add(self,x): self.p.add(self.code[x], 1) self.size += 1 def remove(self,x): self.p.add(self.code[x], -1) self.size -= 1 def order(self,x): """ return x rank in order of decreasing(1-indexed) BIT.order(x) = bisect_left(BIT.sort(),x) + 1 BIT.minimum(BIT.order(x)) = BIT.lower_bound(x) """ if x in self.code.keys(): return self.p.sum(self.code[x]) + 1 else: return self.p.sum(bisect_right(self.data, x)) + 1 def bisect_left(self,x): """ return bisect_left(sorted(B),x) """ if x in self.code.keys(): return self.p.sum(self.code[x]) else: return self.p.sum(bisect_right(self.data, x)) def bisect_right(self,x): """ return bisect_right(sorted(B),x) """ x += 1 if x in self.code.keys(): return self.p.sum(self.code[x]) else: return self.p.sum(bisect_right(self.data, x)) def count(self,x): return self.p[self.code[x]] def minimum(self,k=1): """ return k-th minimum value """ if k <= self.size: return self.decode[self.p.lower_bound(k)[0] + 1] else: sys.stderr.write("minimum: list index out of range (k={0})\n".format(k)) def min(self): return self.minimum(1) def max(self): return self.decode[self.p.lower_bound(self.size)[0] + 1] def upper_bound(self,x,equal=False): """ return maximum element lower than x """ if x in self.code.keys(): y = self.code[x] + equal else: y = bisect_right(self.data, x) k = self.p.sum(y) if k: return self.minimum(k) def lower_bound(self,x,equal=False): """ return minimum element greater than x """ if x in self.code.keys(): y = self.code[x] + 1 - equal else: y = bisect_left(self.data, x-1) k = self.p.sum(y) + 1 if k <= self.size: return self.minimum(k) def __getitem__(self, k): """ return k-th minimum element (0-indexed) B[k] = sorted(A)[k] """ if len(self)==0: sys.stderr.write("__getitem__: no elements exist in this BitSet\n") elif k >= len(self): sys.stderr.write("__getitem__: index (={0}) is larger than the maximum index (={1})\n".format(k,len(self)-1)) elif k >= 0: return self.minimum(k+1) else: sys.stderr.write("__getitem__: index (={0}) is negative \n".format(k)) def __len__(self): return self.size def __iter__(self): """ return sorted list """ for i in range(self.n+1): if self.p[i]: for _ in range(self.p[i]): yield self.decode[i] def __str__(self): """ return sorted list """ text1 = " ".join(list(map(str, self))) return "[" + text1 + "]" class SortedInterval: def __init__(self,data): self.SL = SortedList2(data) self.rs = {} self.length = 0 def add(self, l, r): prev_l = self.SL.upper_bound(l) if prev_l is not None and l <= self.rs[prev_l]: l = prev_l r = max(r, self.rs[prev_l]) del self.rs[prev_l] self.SL.remove(prev_l) removed = [] next_l=self.SL.lower_bound(l) while next_l is not None and next_l<=r: removed.append(next_l) next_l=self.SL.lower_bound(next_l) for next_l in removed: r = max(r, self.rs[next_l]) del self.rs[next_l] self.SL.remove(next_l) self.SL.add(l) self.rs[l] = r # 新しく生成された区間の大きさを返す return r - l def sum(self): res=0 for l in self.SL: res+=self.rs[l]-l+1 return res def __iter__(self): for l in self.SL: yield l, self.rs[l] ######################################################### def example(): global input example = iter( """ 1000000000000000000 2 0 999999999999999999 0 999999999999999999 """ .strip().split("\n")) input = lambda: next(example) ######################################################### import sys input = sys.stdin.readline from bisect import bisect_left, bisect_right # example() N, Q = map(int, input().split()) intervals = [] data=[] for _ in range(Q): l,r=map(int, input().split()) intervals.append((l,r)) data.append(l) data.append(r+1) SI = SortedInterval(data) ans = 0 for l, r in intervals: ans = max(SI.add(l, r + 1), ans) print(ans)