问题描述

Indeed公司有$N$名员工。员工$i (1 ≦ i ≦ N)$ 在时间$S_i$上班，时间$T_i$下班。每个员工在办公室期间会向来上班的员工问候"How are you?"。即，当$S_i < S_j < T_i$时，员工$i$会问候员工$j$。

你打算计算每个员工向多少人问候"How are you?"。

输入

从标准输入中按以下格式给出输入。

$N$ $S_1$ $T_1$ $S_2$ $T_2$ : $S_N$ $T_N$

• 第1行是一个整数$N (1 ≦ N ≦ 10^5)$，表示员工数量。
• 第2行到第N行给出每个员工的上班时间和下班时间。其中第i行包含两个整数$S_i, T_i (1 ≦ S_i < T_i ≦ N*2)$，用空格分隔。表示员工$i$在时间$S_i$上班，时间$T_i$下班。保证不存在满足$S_i = S_j$或$S_i = T_j$的$i,j (1 ≦ i < j ≦ N)$。(16:18删除)
• 给出的上班时间和下班时间全部不同。即$S_1,…,S_N,T_1,…,T_N$都不相等。(16:18添加)

部分分

本问题有部分分。

• 对于满足$N ≦ 2000$的数据集1，如果答案正确，则可获得30分。
• 如果对所有测试用例给出正确答案，则额外可获得70分。

输出

输出由N行组成。其中第i行是一个整数，表示员工$i$向多少人问候"How are you?"。输出末尾应包含换行符。

输入示例1

4
1 6
2 4
3 7
5 8

输出示例1

3
1
1
0

在这个输入示例中，

• 员工1会向员工2、3和4问候"How are you?"。
• 员工2会向员工3问候"How are you?"。
• 员工3会向员工4问候"How are you?"。
• 员工4不会向任何人问候"How are you?"。

输入示例2

7
5 12
10 11
1 2
6 13
4 7
3 8
9 14

输出示例2

3
0
0
2
2
3
1