{"problem":{"name":"J. Segments","description":{"content":"There is a straight line colored in white. _n_ black segments are added on it one by one. After each segment is added, determine the number of connected components of black segments (i. e. the number","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF926J"},"statements":[{"statement_type":"Markdown","content":"There is a straight line colored in white. _n_ black segments are added on it one by one.\n\nAfter each segment is added, determine the number of connected components of black segments (i. e. the number of black segments in the union of the black segments).\n\nIn particular, if one segment ends in a point _x_, and another segment starts in the point _x_, these two segments belong to the same connected component.\n\n## Input\n\nThe first line contains a single integer _n_ (1 ≤ _n_ ≤ 200 000) — the number of segments.\n\nThe _i_\\-th of the next _n_ lines contains two integers _l__i_ and _r__i_ (1 ≤ _l__i_ < _r__i_ ≤ 109) — the coordinates of the left and the right ends of the _i_\\-th segment. The segments are listed in the order they are added on the white line.\n\n## Output\n\nPrint _n_ integers — the number of connected components of black segments after each segment is added.\n\n[samples]\n\n## Note\n\nIn the first example there are two components after the addition of the first two segments, because these segments do not intersect. The third added segment intersects the left segment and touches the right segment at the point 4 (these segments belong to the same component, according to the statements). Thus the number of connected components of black segments is equal to 1 after that.","is_translate":false,"language":"English"}],"meta":{"iden":"CF926J","tags":["data structures"],"sample_group":[["3\n1 3\n4 5\n2 4","1 2 1"],["9\n10 20\n50 60\n30 40\n70 80\n90 100\n60 70\n10 40\n40 50\n80 90","1 2 3 4 5 4 3 2 1"]],"created_at":"2026-03-03 11:00:39"}}