가장 나이 많은 사람

시간 제한3초메모리 제한1024 MB

요약

사람마다 출생 연도가 다르고 사망 연도가 주어질 때, 각 사람이 연말 연설을 한 횟수, 즉 그 해 마지막에 살아 있는 가장 나이 많은 주민이었던 연도의 수를 센다.

난이도: 보통10점 중 7점
유형: 정렬, 구간, 시뮬레이션, 구현
정답자: 아직 제출이 없습니다

문제

아주 오래전, Stackköping이라는 작은 마을이 있었다. Stackköping 주민들에게는 여러 특별한 전통이 있었다. 한 전통은 매년 말에 살아 있는 주민 중 가장 나이가 많은 사람이 신년 연설을 해야 한다는 것이었다. 또 다른 전통은 매년 많아야 한 명의 새 사람만 태어날 수 있다는 것이었고, 일부 전문가에 따르면 결국 이것이 Stackköping의 멸망으로 이어졌다고 한다.

고고학 발굴에서 Stackköping에 살았던 모든 $n$ 명의 출생 연도와 사망 연도를 보여 주는 문서가 발견되었다. 당신은 이 문서를 입수했고, 각 사람이 몇 번의 신년 연설을 했는지 계산하려 한다.

신년 연설은 항상 매년 가장 마지막에 일어나는 일이므로, 같은 해의 신년 연설 이후에는 아무도 태어나거나 죽지 않는다. 신년 시점에 아무도 살아 있지 않다면 당연히 연설은 열리지 않는다. 그렇지 않으면 한 사람만 살아 있어도 항상 연설이 열린다.

입력

첫 번째 줄에는 정수 $n$ ( $1 \le n \le 10^5$ )이 주어진다. 이는 사람 수이다. 다음 $n$ 개의 줄에는 두 정수 $f_i$ 와 $d_i$ ( $0 \le f_i < d_i \le 10^9$ )가 주어진다. 이는 $i$ 번째 사람이 태어난 해와 죽은 해이다. 모든 $f_i$ 는 서로 다르다.

출력

$n$ 개의 줄을 출력한다. 각 줄에는 정수 하나를 출력하며, $i$ 번째 정수는 $i$ 번째 사람이 한 신년 연설의 횟수이다.

예제3

예제 1
입력
```
4
0 3
4 5
2 5
7 8
```
예상 출력
```
3
0
2
1
```

예제 2

입력

7
1763 1844
1799 1859
1826 1872
1829 1907
1858 1950
1882 1973
1946 1000000000

예상 출력

예제 3
입력
```
4
1 5
4 8
5 9
2 6
```
예상 출력
```
4
2
1
1
```