/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
問題文
A 社には N 人の社員が所属しています。
ある日、社員 i は時刻 S_i にオフィスに出社し、時刻 T_i に退社しました。
各 i について、この日 社員 i がオフィスで会った自分以外の社員の数を求めてください。
ただし、社員 i と社員 j が同時にオフィスにいる時間が存在するとき、かつそのときに限り社員 i と社員 j は会ったとみなします。
また、ある社員の退社と同時に別の社員が出社するときも、これらの社員は同時にオフィスに存在したとみなします。
制約
- 2 \leq N \leq 2\times 10^5
- 1 \leq S_i \leq T_i \leq 2\times 10^5
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N S_1 T_1 S_2 T_2 \vdots S_N T_N
出力
社員 i がオフィスで会った自分以外の社員の数を X_i とする。X_1,X_2,\ldots,X_N をこの順に空白区切りで出力せよ。
入力例 1
4 1 10 5 30 10 15 20 40
出力例 1
2 3 2 1
社員 1 は社員 2,3 と、社員 2 は社員 1,3,4 と、社員 3 は社員 1,2 と、社員 4 は社員 2 と会いました。
入力例 2
10 33553 130683 93150 198918 44559 198032 87304 140783 58113 161838 858 74380 39597 150815 2425 149780 8298 10367 37788 184869
出力例 2
8 7 8 7 8 7 8 9 2 8
Problem Statement
Company A has N employees.
One day, employee i arrived at work at time S_i and left there at time T_i.
For each i, find how many other employees met employee i at the office on that day.
Here, employees i and j are considered to have met each other if and only if they were at the office at any moment, even if one arrived at work exactly when the other left there.
Constraints
- 2 \leq N \leq 2\times 10^5
- 1 \leq S_i \leq T_i \leq 2\times 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N S_1 T_1 S_2 T_2 \vdots S_N T_N
Output
If employee i met X_i other employees at the office, print X_1,X_2,\ldots,X_N, separated by spaces.
Sample Input 1
4 1 10 5 30 10 15 20 40
Sample Output 1
2 3 2 1
Employee 1 met employees 2,3; employee 2 met employees 1,3,4; employee 3 met employees 1,2; employee 4 met employee 2.
Sample Input 2
10 33553 130683 93150 198918 44559 198032 87304 140783 58113 161838 858 74380 39597 150815 2425 149780 8298 10367 37788 184869
Sample Output 2
8 7 8 7 8 7 8 9 2 8