星星

题目描述

天文学家经常要检查星星的位置。每颗星星可以用平面上的一个点表示，坐标为：

(x, y)

我们定义一颗星星的级别为：

在所有已经给定的星星中，位置不高于它，并且不在它右边的星星数量。

换句话说，对于一颗星星 (x, y)，如果另一颗星星 (x', y') 满足：

x' <= x 且 y' <= y

那么这颗星星就会被计入 (x, y) 的级别。

现在给出 n 颗星星的坐标，请统计级别为 0, 1, 2, ..., n - 1 的星星分别有多少颗。

---

输入格式

第一行一个整数 n，表示星星的数量。

接下来 n 行，每行两个整数 x, y，表示一颗星星的坐标。

输入数据保证：

星星按照 y 从小到大的顺序给出；
如果 y 相同，则按照 x 从小到大的顺序给出。

---

输出格式

输出 n 行。

第 i + 1 行输出级别为 i 的星星数量。

也就是说，依次输出：

级别为 0 的星星数量
级别为 1 的星星数量
级别为 2 的星星数量
...
级别为 n - 1 的星星数量

---

数据范围

1 <= n <= 15000
0 <= x <= 32000
0 <= y <= 32000

---

样例输入

5
1 1
5 1
7 1
3 3
5 5

样例输出

1
2
1
1
0

---

样例解释

按照输入顺序处理这 5 颗星星。

因为输入已经按照 y 从小到大排序，所以在处理当前星星时，之前出现过的星星一定满足：

y' <= y

因此，我们只需要统计之前出现过的星星中有多少颗满足：

x' <= x

这个数量就是当前星星的级别。

---

第 1 颗星星：(1, 1)

之前没有星星。

所以级别为：

0

---

第 2 颗星星：(5, 1)

之前有：

(1, 1)

满足：

1 <= 5 且 1 <= 1

所以级别为：

1

---

第 3 颗星星：(7, 1)

之前有：

(1, 1), (5, 1)

它们都满足 x' <= 7。

所以级别为：

2

---

第 4 颗星星：(3, 3)

之前有：

(1, 1), (5, 1), (7, 1)

其中只有：

(1, 1)

满足 x' <= 3。

所以级别为：

1

---

第 5 颗星星：(5, 5)

之前有：

(1, 1), (5, 1), (7, 1), (3, 3)

其中满足 x' <= 5 的有：

(1, 1), (5, 1), (3, 3)

所以级别为：

3

因此各级别的数量为：

级别	星星数量
0	1
1	2
2	1
3
4	0

所以输出：

1
2
1
1
0