Problem
흰색으로 칠해진 직선이 있습니다. n 개의 검정색 세그먼트가 하나씩 추가됩니다.
각 세그먼트 추가 후 연결된 블랙 세그먼트 수(즉, 합집합의 블랙 세그먼트 수)를 결정합니다.
특히 한 세그먼트가 x 지점에서 끝나고 다른 세그먼트가 x 지점에서 시작하는 경우 이 두 세그먼트가 동일한 연결된 구성 요소에 있다는 점을 고려하세요.
입력
첫 번째 줄은 정수 n (1 ≤ n ≤ 200 000) — 세그먼트 수.
다음 n행의 i번째에는 두 개의 정수 li 및 ri(1 ≤ li < ri ≤ 109) — 세그먼트 번호 i의 왼쪽과 오른쪽 끝의 좌표. 세그먼트는 흰색 선에 추가된 순서대로 나열됩니다.
출력
n 정수 인쇄 — 세그먼트를 추가할 때마다 검은색 세그먼트에서 연결된 구성요소의 수.
예
<헤드>
| # |
입력 |
출력 |
<몸>
| 1 |
<사업부>3
1 3
4 5
2 4
|
1 2 1 |
| 2 |
9
10 20
50 60
30 40
70 80
90 100
60 70
10 40
40 50
80 90
|
1 2 3 4 5 4 3 2 1 |