Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

This round has an unusual addition to the rules. For each problem you must use distinct language. Thus, if you have a submission that has passed at least one test or is being tested at the moment, then for this task you can use only this language and can not use it for other tasks. More details can be read by the link. Different implementations of the same language are considered to be the same language (for example, in C++ you can only solve one problem, regardless of the exact chosen compiler).

No tag edit access

J. Segments

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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 of black segments in the union of the black segments).

In 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.

Input

The first line contains a single integer *n* (1 ≤ *n* ≤ 200 000) — the number of segments.

The *i*-th of the next *n* lines contains two integers *l*_{i} and *r*_{i} (1 ≤ *l*_{i} < *r*_{i} ≤ 10^{9}) — 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.

Output

Print *n* integers — the number of connected components of black segments after each segment is added.

Examples

Input

3

1 3

4 5

2 4

Output

1 2 1

Input

9

10 20

50 60

30 40

70 80

90 100

60 70

10 40

40 50

80 90

Output

1 2 3 4 5 4 3 2 1

Note

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.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/24/2019 02:38:18 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|