← 返回题目列表

Codeforces · 652/D

D. 嵌套段

中文机器翻译题面 查看原题

一条线上有 n 段。某些线段的端点没有重合。对于每个段,找出它包含的段数。

输入

第一行包含一个整数 n (1 ≤ n ≤ 2·105) — 一行上的段数。

接下来的 n 行中的每一行都包含两个整数 li 和 ri (- 109 ≤ li < ri ≤ 109) — 第 i 段的左端和右端的坐标。保证某些线段的端点不会重合。

输出

打印 n 行。其中第 j 个应该包含唯一的整数 aj — 第 j 个段中包含的段数。

示例

输入 #1

4
1 8
2 3
4 7
5 6

输出 #1

3
0
1
0

输入 #2

3
3 4
1 5
2 6

输出 #2

0
1
1