TC

Some of the more elite (and not-so-elite) coders around take part in a contest called TC. In TC, there are multiple types of competitions. Here, we consider the Algorithm and TCHS competition types. For each type, each competitor receives a rating, an integer between 1 and 100000, inclusive. A coder's rating is based upon his or her level of performance in single round matches (SRMs) and is calculated using a complicated formula.

Each SRM has three problems, usually called the 250, 500, and 1000 because of their most frequently occurring point values, although they can sometimes have slightly different values, such as 300, 550, and 900. In Algorithm SRMs, the 250 is usually fairly easy, the 500 requires some thought, and can be quite difficult, and the 1000 is usually very difficult, accessible only to those with an advanced knowledge of algorithms and well-honed problem-solving skills. In TCHS SRMs, in which only high school students are allowed to participate, the 250 and 500 are usually fairly easy, and the 1000 is most often not harder than an average problem from a typical national olympiad contest.

The interesting thing is that there's a speed factor too - a coder gets no points for a solution if it is even slightly wrong (i.e. does not pass all of the test cases). Instead, partial scoring is based upon the time taken for a coder to submit his or her final solution for that problem. A coder who solves the 250 and 500 quickly may earn more points than a coder who solves only the 1000, but takes a long time to do so.

Although the TCHS and Algorithm ratings for a coder who has participated in both TCHS and Algorithm SRMs lately are usually close, this is not always the case. In particular, TCHS is more about speed, since many coders are able to solve all three problems, whereas Algorithm SRMs require more thinking and there is a steeper curve in terms of problem difficulty.

Problem Statement
You are given N coders (1 ≤ N ≤ 300000), conveniently numbered from 1 to N. Each of these coders participates in both TCHS and Algorithm contests. For each coder, you are also given an Algorithm rating A_i and a TCHS rating H_i. Coder i is said to be better than coder j if and only if both of coder i's ratings are greater than or equal to coder j's corresponding ratings, with at least one being greater. For each coder i, determine how many coders coder i is better than.

Input Format
On the first line of input is a single integer N, as described above.
N lines then follow. Line i+1 contains two space-separated integers, A_i and H_i.

Output Format
Line i should contain the number of coders that coder i is better than.

Sample Input

9
2156 1789 
862 700 
1106 1041 
1568 1557 
2575 1984 
1033 950 
1738 1649 
1097 1089 
1774 1630 

Sample Output

7
0
2
4
8
1
5
2
5

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Jan 27, 2009
Author: bbi5291

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)