import bisect def main(): import sys input = sys.stdin.read data = input().split() idx = 0 D = int(data[idx]) idx += 1 Q = int(data[idx]) idx += 1 queries = [] for _ in range(Q): A = int(data[idx]) B = int(data[idx+1]) queries.append((A, B)) idx += 2 intervals = [] max_len = 0 for A, B in queries: if not intervals: new_start, new_end = A, B current_length = new_end - new_start + 1 if current_length > max_len: max_len = current_length bisect.insort(intervals, (new_start, new_end)) print(max_len) continue starts = [interval[0] for interval in intervals] i = bisect.bisect_left(starts, A) new_start = A new_end = B left = i - 1 while left >= 0 and intervals[left][1] >= new_start - 1: new_start = min(intervals[left][0], new_start) new_end = max(intervals[left][1], new_end) left -= 1 right = i while right < len(intervals) and intervals[right][0] <= new_end + 1: new_end = max(new_end, intervals[right][1]) right += 1 del_start = left + 1 del_end = right if del_start < del_end: del intervals[del_start:del_end] bisect.insort(intervals, (new_start, new_end)) current_length = new_end - new_start + 1 if current_length > max_len: max_len = current_length print(max_len) if __name__ == "__main__": main()