{"raw_statement":[{"iden":"statement","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."},{"iden":"input","content":"The 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."},{"iden":"output","content":"Print _n_ integers — the number of connected components of black segments after each segment is added."},{"iden":"examples","content":"Input\n\n3\n1 3\n4 5\n2 4\n\nOutput\n\n1 2 1 \n\nInput\n\n9\n10 20\n50 60\n30 40\n70 80\n90 100\n60 70\n10 40\n40 50\n80 90\n\nOutput\n\n1 2 3 4 5 4 3 2 1"},{"iden":"note","content":"In 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."}],"translated_statement":[{"iden":"statement","content":"有一条白色直线。依次向其上添加 #cf_span[n] 个黑色线段。\n\n在每个线段添加后，确定黑色线段的连通分量数量（即黑色线段并集中的线段段数）。\n\n特别地，如果一个线段的右端点为 #cf_span[x]，另一个线段的左端点也为 #cf_span[x]，则这两个线段属于同一个连通分量。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]）——线段的数量。\n\n接下来的 #cf_span[n] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li < ri ≤ 109]）——第 #cf_span[i] 个线段的左端点和右端点坐标。线段按添加顺序列出。\n\n请输出 #cf_span[n] 个整数——每个线段添加后，黑色线段的连通分量数量。\n\n在第一个例子中，前两个线段添加后有两个连通分量，因为它们不相交。第三个添加的线段与左侧线段相交，并在点 #cf_span[4] 处接触右侧线段（根据题意，这两个线段属于同一连通分量）。因此，此时黑色线段的连通分量数量为 #cf_span[1]。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 200 000]）——线段的数量。第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li < ri ≤ 109]）——第 #cf_span[i] 个线段的左端点和右端点坐标。线段按添加顺序列出。"},{"iden":"output","content":"请输出 #cf_span[n] 个整数——每个线段添加后，黑色线段的连通分量数量。"},{"iden":"examples","content":"输入31 34 52 4输出1 2 1 输入910 2050 6030 4070 8090 10060 7010 4040 5080 90输出1 2 3 4 5 4 3 2 1 "},{"iden":"note","content":"在第一个例子中，前两个线段添加后有两个连通分量，因为它们不相交。第三个添加的线段与左侧线段相交，并在点 #cf_span[4] 处接触右侧线段（根据题意，这两个线段属于同一连通分量）。因此，此时黑色线段的连通分量数量为 #cf_span[1]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of segments.  \nLet $ S_i = [l_i, r_i] \\subset \\mathbb{R} $ be the $ i $-th closed interval (segment) added, with $ 1 \\leq l_i < r_i \\leq 10^9 $, for $ i = 1, \\dots, n $.  \n\nLet $ C_i $ denote the number of connected components of the union $ \\bigcup_{j=1}^i S_j $ after the $ i $-th segment is added.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 200{,}000 $  \n2. For all $ i \\in \\{1, \\dots, n\\} $: $ 1 \\leq l_i < r_i \\leq 10^9 $  \n\n**Objective**  \nFor each $ i \\in \\{1, \\dots, n\\} $, compute $ C_i $, where two segments are in the same connected component if their closures intersect (i.e., $ [a,b] \\cap [c,d] \\neq \\emptyset $ implies they are connected; in particular, $ b = c $ suffices for connection).  \n\nThe output is the sequence $ C_1, C_2, \\dots, C_n $.","simple_statement":null,"has_page_source":false}