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.flip = 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 self.flip += self.size - self.p.sum(self.code[x]+1) # we can remove this if we do not use flip_number def remove(self,x): self.p.add(self.code[x], -1) self.size -= 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 count_range(self,l,r): """ return number of elements in closed set [l,r]""" return self.bisect_right(r)-self.bisect_left(l) 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) k = self.p.sum(y) + 1 if k <= self.size: return self.minimum(k) def nearest(self,x,k): """ return k-th nearest value to x """ if k>len(self): sys.stderr.write("nearest: k (= {0}) is larger than the size of this BitSet\n".format(k)) return def test(d): r=self.bisect_right(x+d)-1 l=self.bisect_left(x-d) return r-l+1<=k ok,ng=0,10**18+1 while abs(ok-ng)>1: mid=(ok+ng)//2 if test(mid): ok=mid else: ng=mid d=ok r=self.bisect_right(x+d)-1 l=self.bisect_left(x-d) if d==0: R=self.lower_bound(x,equal=True) L=self.upper_bound(x,equal=True) if abs(x-L)==abs(R-x): if self.count(L)>=k: return L else: return R elif abs(x-L)=len(self)-1: return self[l-1] else: R=self[r+1] L=self[l-1] if abs(x-L)==abs(R-x): if self.count(L)>=k-(r-l+1): return L else: return R elif abs(x-L)= 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): """ [l,r) = [l,rs[l]) """ prev_l = self.SL.upper_bound(l) if prev_l is not None and l <= self.rs[prev_l]: l = prev_l r = max2(r, self.rs[l]) del self.rs[l] self.SL.remove(l) next_l_key=self.SL.bisect_left(l) removed=[] for i in range(next_l_key,len(self.SL)): next_l = self.SL[i] if next_l>r: break removed.append(next_l) if removed: r=max2(r,self.rs[removed[-1]]) for next_l in removed: del self.rs[next_l] self.SL.remove(next_l) self.SL.add(l) self.rs[l] = r return r - l def remove(self, l, r): """ [l,r) = [l,rs[l]) """ prev_l = self.SL.upper_bound(l) if prev_l is not None and l <= self.rs[prev_l]: self.rs[prev_l] = l next_l_key=self.SL.bisect_left(l) removed=[] for i in range(next_l_key,len(self.SL)): next_l = self.SL[i] if self.rs[next_l]>r: break removed.append(next_l) for next_l in removed: del self.rs[next_l] self.SL.remove(next_l) if r in self: l0,r0=self.edge(r) self.SL.remove(l0) self.SL.add(r) self.rs[r] = r0 def sum(self): """ return size of all intervals""" res=0 for l in self.SL: res+=self.rs[l]-l+1 return res def edge(self, x): l = self.SL.upper_bound(x,equal=True) if l is None: return None r = self.rs[l] if l<=x y else y ######################################################### def example(): global input example = iter( """ 30 12 10 10 15 15 10 11 14 15 14 16 9 11 12 14 13 17 19 29 13 18 11 29 0 13 """ .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 = [] decode=[] # 座圧用 for _ in range(Q): l,r=map(int, input().split()) intervals.append((l,r)) decode.append(l) SI = SortedInterval(decode) ans = 0 for l, r in intervals: ans = max(SI.add(l, r + 1), ans) print(ans)