Problem1573--保护防御塔

1573: 保护防御塔

[Creator : ]
Time Limit : 2 sec  Memory Limit : 128 MB

Description

敌人来啦,快修建防御塔来抵御他们。
假设每座防御能够保护它左下方的其他防御塔(横纵坐标不大于本身)。现在给出n个防御塔的x y坐标,要你求出保护对象个数为0,1,2……n-1的防御塔的个数。

Input

第一行,一个正整数n(1<=n<=15000)
接下来n行,每行两个数xi,yi,代表第i个点的坐标
(1<=xi,yi<=32000)
注意:可能包含多重防御塔的情况(即有数个点在同一坐标)

Output

输出n行,分别代表保护对象为0,1,2……n-1的防御塔的个数。


Sample Input Copy

5
1 1
5 1
7 1
3 3
5 5

Sample Output Copy

1
2
1
1
0

HINT

树状数组

Source/Category