TopCoder

User's AC Ratio

75.0% (3/4)

Submission's AC Ratio

50.0% (3/6)

Tags

Description

西元21世紀是個人口爆炸的世代,西元22世紀亦是如此。

世界上的人口已經超過100億了,因此聯合國昭告世界各國進行人口篩選,只選擇有優勢的一群人,剩下的全部送上火星。
怎樣是「有優勢的」人呢?我們知道身為地球人,每個人有兩項特質,也就是身高與體重,我們稱身高與體重$(h,w)$的人是有優勢的,若且唯若不存在任何一個人$(h', w')$,使得$h'<h\land w'\le w$或$h'\le h\land w'<w$成立。

而你,被派遣調查人口的稽查委員,希望知道在目前觀察到的人口中,有幾個是有優勢的。
(溫馨小提示:$\land$ 是且的意思喔~)

Input Format

輸入第一行包含正整數$N$,代表你將進行$N$次觀察。
接著$N$行每行包含兩個整數$h_i,w_i$,代表第$i$次觀察到的人的身高與體重。

Output Format

對於每次觀察,輸出目前的優勢人口數量。

Sample Input

5
11 20
20 10
20 10
100 20
1 1

Sample Output

1
2
3
3
1

Hints

For $10\%$ of the testdata: $N\le 100$
For $50\%$ of the testdata: $N\le 1000$
For $100\%$ of the testdata: $N\le 10000$
For $100\%$ of the testdata: $\forall 1\le i\le N,h_i,w_i\le10^ 4$

Problem Source

UVa
Set by waynetu

Subtasks

For Testdata: 0 ~ 3, Score: 10
For Testdata: 4 ~ 7, Score: 40
For Testdata: 8 ~ 15, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536